Yuan Mei
ABSTRACT
Composite (or Complex) event processing (CEP) systems search sequences of incoming events for occurrences of user-specified event patterns. Recently, they have gained more attention in a variety of areas due to their powerful and expressive query language and performance potential. Sequentiality (temporal ordering) is the primary way in which CEP systems relate events to each other. In this paper, we present a CEP system called ZStream to efficiently process such sequential patterns. Besides simple sequential patterns, ZStream is also able to detect other patterns, including conjunction, disjunction, negation and Kleene closure.
Unlike most recently proposed CEP systems, which use non-deterministic finite automata (NFA's) to detect patterns, ZStream uses tree-based query plans for both the logical and physical representation of query patterns. By carefully designing the underlying infrastructure and algorithms, ZStream is able to unify the evaluation of sequence, conjunction, disjunction, negation, and Kleene closure as variants of the join operator. Under this framework, a single pattern in ZStream may have several equivalent physical tree plans, with different evaluation costs. We propose a cost model to estimate the computation costs of a plan. We show that our cost model can accurately capture the actual runtime behavior of a plan, and that choosing the optimal plan can result in a factor of four or more speedup versus an NFA based approach. Based on this cost model and using a simple set of statistics about operator selectivity and data rates, ZStream is able to adaptively and seamlessly adjust the order in which it detects patterns on the fly. Finally, we describe a dynamic programming algorithm used in our cost model to efficiently search for an optimal query plan for a given pattern.
- Event Processing Workshop, March 2008. http://complexevents.com/?page_id=87.Google Scholar
- StreamBase corporate homepage, 2009. http://www.streambase.com/.Google Scholar
- Coral8 corporate homepage, 2009. http://www.coral8.com/.Google Scholar
- J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. Efficient pattern matching over event streams. In SIGMOD, 2008. Google ScholarDigital Library
- S. Chakravarthy, V. Krishnaprasad, E. Anwar, and S. Kim. Composite events for active databases: Semantics, contexts and detection. In VLDB, 1994. Google ScholarDigital Library
- U. Dayal et al. The hipac pro ject: Combining active databases and timing constraints. SIGMOD RECORD, 17(1):51--70, March 1988. Google ScholarDigital Library
- A. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and W. White. Cayuga: A general purpose event monitoring system. In CIDR, January 2007.Google Scholar
- F. Fabret, A. Jacobsen, F. Llirbat, J. Pereira, K. Ross, and D. Shasha. Filtering algorithms and implementation for very fast publish/subscribe systems. In SIGMOD, 2001. Google ScholarDigital Library
- S. Gatziu and K. Dittrich. Events in an active ob ject--oriented database. In Workshop on Rules in Database Systems, 1994.Google ScholarCross Ref
- N. Gehani and H. V. Jagadish. Ode as an active database: Constraints and triggers. In VLDB, September 1991. Google ScholarDigital Library
- S. Madden, M. Shah, J. Hellerstein, and V. Raman. Continuously adaptive continuous queries over streams. In SIGMOD, 2002. Google ScholarDigital Library
- A. Ma jumder, R. Rastogi, and S. Vanama. Scalable regular expression matching on data streams. In SIGMOD, 2008. Google ScholarDigital Library
- R. Sadri, C. Zaniolo, A. Zarkesh, and J. Adibi. Expressing and optimizing sequence queries in database systems. ACM TODS, 29(2), June 2004. Google ScholarDigital Library
- P. Selinger et al. Access path selection in a relational database management system. In SIGMOD, 1979. Google ScholarDigital Library
- E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In SIGMOD, 2006. Google ScholarDigital Library
- Y. Zhu, E. Rundensteiner, and G. Heineman. Dynamic plan migration for continuous queries over data streams. In SIGMOD, 2004 Google ScholarDigital Library
Index Terms
- ZStream: a cost-based query processor for adaptively detecting composite events
Recommendations
E-Cube: multi-dimensional event sequence analysis using hierarchical pattern query sharing
SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of dataMany modern applications, including online financial feeds, tag-based mass transit systems and RFID-based supply chain management systems transmit real-time data streams. There is a need for event stream processing technology to analyze this vast amount ...
APAM: Adaptive Eager-Lazy Hybrid Evaluation of Event Patterns for Low Latency
CIKM '16: Proceedings of the 25th ACM International on Conference on Information and Knowledge ManagementEvent pattern detection refers to identifying combinations of events matched to a user-specified query event pattern from a real-time event stream. Latency is an important measure of the performance of an event pattern detection system. Existing methods ...
A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions
SIGMOD '21: Proceedings of the 2021 International Conference on Management of DataEfficiently evaluating a large number of arbitrary Boolean expressions is needed in many applications such as advertising exchanges, complex event processing, and publish/subscribe systems. However, most solutions can support only conjunctive Boolean ...
Comments