skip to main content
10.1145/2675743.2771832acmconferencesArticle/Chapter ViewAbstractPublication PagesdebsConference Proceedingsconference-collections
research-article
Best Paper

Lazy evaluation methods for detecting complex events

Published:24 June 2015Publication History

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.

References

  1. http://www.eoddata.com.Google ScholarGoogle Scholar
  2. A. Adi and O. Etzion. Amit - the situation manager. The VLDB Journal, 13(2):177--203, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  4. M. Akdere, U. Çetintemel, and N. Tatbul. Plan-based complex event detection across distributed sources. Proc. VLDB Endow., 1(1):66--77, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  6. 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 ScholarGoogle ScholarCross RefCross Ref
  7. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  8. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  9. 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 ScholarGoogle Scholar
  10. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  11. G. Cugola and A. Margara. Tesla: a formally defined event specification language. In DEBS, pages 50--61. ACM, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  13. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  14. A. Demers, J. Gehrke, and B. P. Cayuga: A general purpose event monitoring system. In In CIDR, pages 412--422, 2007.Google ScholarGoogle Scholar
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. O. Etzion and P. Niblett. Event Processing in Action. Manning Publications Co., Greenwich, USA, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  18. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  19. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  20. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  21. T. S. Group. Stream: The stanford stream data manager. Technical Report 2003-21, Stanford InfoLab, 2003.Google ScholarGoogle Scholar
  22. D. Gyllstrom, J. Agrawal, Y. Diao, and N. Immerman. On supporting kleene closure over event streams. In ICDE, pages 1391--1393. IEEE, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  24. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  25. M. R. Mendes, P. Bizarro, and P. Marques. Fincos: Benchmark tools for event processing systems.Google ScholarGoogle Scholar
  26. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  27. N. P. Schultz-Møller, M. M., and P. R. Pietzuch. Distributed complex event processing with query rewriting. In DEBS, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  29. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  30. E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In SIGMOD Conference, pages 407--418. ACM, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. 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 ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Lazy evaluation methods for detecting complex events

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      DEBS '15: Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems
      June 2015
      385 pages
      ISBN:9781450332866
      DOI:10.1145/2675743

      Copyright © 2015 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 24 June 2015

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      Overall Acceptance Rate130of553submissions,24%

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader