Karen Walzer
ABSTRACT
Complex Event Processing is an important technology for information systems with a broad application space ranging from supply chain management, systems monitoring, and stock market analysis to news services. Its purpose is the identification of event patterns with logical, temporal or causal relationships within multiple occurring events.
The Rete algorithm is commonly used in rule-based systems to trigger certain actions if a corresponding rule holds. Its good performance for a high number of rules in the rulebase makes it ideally suited for complex event detection. However, the traditional Rete algorithm is limited to operations such as unification and the extraction of predicates from a knowledge base. There is no support for temporal operators.
We propose an extension of the Rete algorithm to support the detection of relative temporal constraints. Further, we propose an efficient means to perform the garbage collection in the Rete algorithm in order to discard events after they can no longer fulfill their temporal constraints. Finally, we present an extension of Allen's thirteen operators for time-intervals with quantitative constraints to deal with too restrictive or too permissive operators by introducing tolerance limits or restrictive conditions for them.
- J. F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26:832--843, 1983. Google Scholar
Digital Library
- B. Berstel. Extending the RETE Algorithm for Event Management. In TIME '02: Proceedings of the Ninth International Symposium on Temporal Representation and Reasoning (TIME'02), page 49, Washington, DC, USA, 2002. IEEE Computer Society. Google ScholarDigital Library
- M. H. Bohlen, R. Busatto, and C. S. Jensen. Point-versus interval-based temporal data models. In ICDE, pages 192--200, 1998. Google ScholarDigital Library
- F. Bry and M. Eckert. Temporal order optimizations of incremental joins for composite event detection. In Proceedings of Inaugural Int. Conference on Distributed Event-Based Systems, Toronto, Canada (20th--22nd June 2007). ACM, 2007. Google ScholarDigital Library
- A. J. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and W. M. White. Cayuga: A general purpose event monitoring system. In CIDR, pages 412--422, 2007.Google Scholar
- C. Forgy. Rete: A fast algorithm for the many patterns/many objects match problem. Artif. Intell., 19(1):17--37, 1982.Google ScholarDigital Library
- A. Galton and J. Augusto. Two approaches to event definition. In Lecture Notes In Computer Science. Proceedings of the 13th International Conference on Database and Expert Systems Applications, volume 2453, pages 547--556, 2002. Google ScholarDigital Library
- JBoss. JBoss Rules, 2007. http://labs.jboss.com/drools/.Google Scholar
- L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, July 1978. Google ScholarDigital Library
- G. Li and H.-A. Jacobsen. Composite subscriptions in content-based publish/subscribe systems. In Middleware, pages 249--269, 2005. Google ScholarDigital Library
- M. A. Maloof and K. Kochut. Modifying Rete to Reason Temporally. In ICTAI, pages 472--473, 1993.Google ScholarCross Ref
- I. Meiri. Combining qualitative and quantitative constraints in temporal reasoning. In T. Dean and K. McKeown, editors, Proceedings of the Ninth National Conference on Artificial Intelligence, pages 260--267, Menlo Park, California, 1991. AAAI Press.Google Scholar
- Red Hat, Inc. Drools development branch for temporal reasoning. Online. http://anonsvn.labs.jboss.com/labs/jbossrules/branches/temporal_rete/.Google Scholar
- U. Srivastava and J. Widom. Flexible time management in data stream systems. In PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 263--274, New York, NY, USA, 2004. ACM Press. Google ScholarDigital Library
- D. Teodosiu and G. Pollak. Discarding unused temporal information in a production system. In Proc. of the ISMM International Conference on Information and Knowledge Management CIKM-92, pages 177--184, Baltimore, MD, 1992.Google Scholar
- M. Vilain, H. Kautz, and P. van Beek. Constraint propagation algorithms for temporal reasoning: a revised report. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1990.Google ScholarCross Ref
- W. M. White, M. Riedewald, J. Gehrke, and A. J. Demers. What is "next" in event processing? In PODS, pages 263--272. ACM, 2007. Google ScholarDigital Library
- E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pages 407--418, New York, NY, USA, 2006. ACM Press. Google ScholarDigital Library
- E. Yoneki and J. Bacon. Unified semantics for event correlation over time and space in hybrid network environments. In OTM Conferences (1), pages 366--384, 2005. Google ScholarDigital Library
Index Terms
- Relative temporal constraints in the Rete algorithm for complex event detection
Recommendations
Temporal constraints for rule-based event processing
PIKM '07: Proceedings of the ACM first Ph.D. workshop in CIKMComplex event processing (CEP) is an important technology for event-driven systems with a broad application space ranging from supply chain management for RFID, systems monitoring, and stock market analysis to news services. The purpose of CEP is the ...
Developing event-condition-action rules in real-time active database
SAC '07: Proceedings of the 2007 ACM symposium on Applied computingTraditional event-condition-action (ECA) rules in real-time active database (RTADB) lack the capabilities to express complicated quantitative temporal information in the system. To solve this problem, in this paper, we present graphical ECA rules with a ...
Time to the Rescue - Supporting Temporal Reasoning in the Rete Algorithm for Complex Event Processing
DEXA '08: Proceedings of the 19th international conference on Database and Expert Systems ApplicationsComplex event processing is an important technology with possible application in supply chain management and business activity monitoring. Its basis is the identification of event patterns within multiple occurring events having logical, causal or ...
Comments