ABSTRACT
The goal of Complex Event Processing (CEP) systems is to efficiently detect complex patterns over a stream of primitive events. A pattern of particular significance is a sequence, where we are interested in identifying that a number of primitive events have arrived on the stream in a predefined order. Many popular CEP systems employ Non-deterministic Finite Automata (NFA) arranged in a chain topology to detect such sequences. Existing NFA-based mechanisms incrementally extend previously observed prefixes of a sequence until a match is found. Consequently, each newly arriving event needs to be processed to determine whether a new prefix is to be initiated or an existing one extended. This approach may be very inefficient when events at the beginning of the sequence are very frequent.
We address the problem by introducing a lazy evaluation mechanism that is able to process events in descending order of selectivity. We employ this mechanism in a chain topology NFA, which waits until the most selective event in the sequence arrives and then adds events to partial matches according to a predetermined order of selectivity. In addition, we propose a tree topology NFA that does not require the selectivity order to be defined in advance. Finally, we experimentally evaluate our mechanism on real-world stock trading data, demonstrating a performance gain of two orders of magnitude, with significantly reduced memory resource requirements.
- http://www.eoddata.com.Google Scholar
- A. Adi and O. Etzion. Amit - the situation manager. The VLDB Journal, 13(2):177--203, 2004. Google ScholarDigital Library
- J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. Efficient pattern matching over event streams. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pages 147--160. Google ScholarDigital Library
- M. Akdere, U. Çetintemel, and N. Tatbul. Plan-based complex event detection across distributed sources. Proc. VLDB Endow., 1(1):66--77, 2008. Google ScholarDigital Library
- A. Arasu, S. Babu, and J. Widom. The cql continuous query language: Semantic foundations and query execution. The VLDB Journal, 15(2):121--142, 2006. Google ScholarDigital Library
- A. Artikis, C. Baber, P. Bizarro, C. Canudas de Wit, O. Etzion, F. Fournier, P. Goulart, A. Howes, J. Lygeros, G. Paliouras, A. Schuster, and I. Sharfman. Scalable proactive event-driven decision making. IEEE Technol. Soc. Mag., 33(3):35--41, 2014.Google ScholarCross Ref
- L. Brenna, A. Demers, J. Gehrke, M. Hong, J. Ossher, B. Panda, M. Riedewald, M. Thatte, and W. White. Cayuga: A high-performance event processing engine. In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, pages 1100--1102. ACM. Google ScholarDigital Library
- C. Y. Chan, P. Felber, M. N. Garofalakis, and R. Rastogi. Efficient filtering of xml documents with xpath expressions. VLDB J., 11(4):354--379, 2002. Google ScholarDigital Library
- S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. A. Shah. Telegraphcq: Continuous dataflow processing for an uncertain world. In CIDR, 2003.Google Scholar
- J. Chen, D. J. DeWitt, F. Tian, and Y. Wang. Niagaracq: A scalable continuous query system for internet databases. SIGMOD Rec., 29(2):379--390, 2000. Google ScholarDigital Library
- G. Cugola and A. Margara. Tesla: a formally defined event specification language. In DEBS, pages 50--61. ACM, 2010. Google ScholarDigital Library
- G. Cugola and A. Margara. Processing flows of information: From data stream to complex event processing. ACM Comput. Surv., 44(3):15:1--15:62, 2012. Google ScholarDigital Library
- A. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. White. Towards expressive publish/subscribe systems. In Proceedings of the 10th International Conference on Advances in Database Technology, pages 627--644. Springer-Verlag. Google ScholarDigital Library
- A. Demers, J. Gehrke, and B. P. Cayuga: A general purpose event monitoring system. In In CIDR, pages 412--422, 2007.Google Scholar
- C. Dousson and P. L. Maigat. Chronicle recognition improvement using temporal focusing and hierarchization. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 324--329, 2007. Google ScholarDigital Library
- O. Etzion and P. Niblett. Event Processing in Action. Manning Publications Co., Greenwich, USA, 2010. Google ScholarDigital Library
- B. Gedik, H. Andrade, K. L. Wu, P. S. Yu, and M. Doo. Spade: the system s declarative stream processing engine. In SIGMOD Conference, pages 1123--1134. ACM, 2008. Google ScholarDigital Library
- N. Giatrakos, A. Deligiannakis, M. Garofalakis, I. Sharfman, and A. Schuster. Distributed geometric query monitoring using prediction models. ACM Trans. Database Syst., 39(2):16, 2014. Google ScholarDigital Library
- B. Gilburd, A. Schuster, and R. Wolff. Privacy-preserving data mining on data grids in the presence of malicious participants. In 13th International Symposium on High-Performance Distributed Computing), pages 225--234, 2004. Google ScholarDigital Library
- T. J. Green, A. Gupta, G. Miklau, M. Onizuka, and D. Suciu. Processing XML streams with deterministic automata and stream indexes. ACM Trans. Database Syst., 29(4):752--788, 2004. Google ScholarDigital Library
- T. S. Group. Stream: The stanford stream data manager. Technical Report 2003-21, Stanford InfoLab, 2003.Google Scholar
- D. Gyllstrom, J. Agrawal, Y. Diao, and N. Immerman. On supporting kleene closure over event streams. In ICDE, pages 1391--1393. IEEE, 2008. Google ScholarDigital Library
- A. Lazerson, I. Sharfman, D. Keren, A. Schuster, M. Garofalakis, and V. Samoladas. Monitoring distributed streams using convex decompositions. Proc. VLDB Endow., 8(5):545--556, 2015. Google ScholarDigital Library
- Y. Mei and S. Madden. Zstream: a cost-based query processor for adaptively detecting composite events. In Proceedings of the 29th ACM SIGMOD Conference, pages 193--206. ACM, 2009. Google ScholarDigital Library
- M. R. Mendes, P. Bizarro, and P. Marques. Fincos: Benchmark tools for event processing systems.Google Scholar
- R. Sadri, C. Zaniolo, A. Zarkesh, and J. Adibi. Expressing and optimizing sequence queries in database systems. ACM Trans. Database Syst., 29(2):282--318, 2004. Google ScholarDigital Library
- N. P. Schultz-Møller, M. M., and P. R. Pietzuch. Distributed complex event processing with query rewriting. In DEBS, 2009. Google ScholarDigital Library
- I. Sharfman, A. Schuster, and D. Keren. A geometric approach to monitoring threshold functions over distributed data streams. ACM Trans. Database Syst., 32(4), 2007. Google ScholarDigital Library
- F. Wang and P. Liu. Temporal management of rfid data. In Proceedings of the 31st International Conference on Very Large Data Bases, VLDB '05, pages 1128--1139. VLDB Endowment, 2005. Google ScholarDigital Library
- E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In SIGMOD Conference, pages 407--418. ACM, 2006. Google ScholarDigital Library
- H. Zhang, Y. Diao, and N. Immerman. On complexity and optimization of expensive queries in complex event processing. In SIGMOD, pages 217--228, 2014. Google ScholarDigital Library
Index Terms
Lazy evaluation methods for detecting complex events
Recommendations
Join query optimization techniques for complex event processing applications
Complex event processing (CEP) is a prominent technology used in many modern applications for monitoring and tracking events of interest in massive data streams. CEP engines inspect real-time information flows and attempt to detect combinations of ...
Clustering Events on Streams Using Complex Context Information
ICDMW '08: Proceedings of the 2008 IEEE International Conference on Data Mining WorkshopsMonitoring applications play an increasingly important role in many domains. They detect events in monitored systems and take actions such as invoke a program or notify an administrator. Often administrators must then manually investigate events to ...
Supporting Interval Time Complex Events Processing in an RFID System
AbstractRadio Frequency Identification (RFID) is a prevalent wireless identification technology that collects identity information from RFID tags to RFID readers. Complex events processing is an important technique in RFID systems to define the systems ...
Comments