Haopeng Zhang
Neil Immerman
Abstract
Large-scale event systems are becoming increasingly popular in a variety of domains. Event pattern evaluation plays a key role in monitoring applications in these domains. Existing work on pattern evaluation, however, assumes that the occurrence time of each event is known precisely and the events from various sources can be merged into a single stream with a total or partial order. We observe that in real-world applications event occurrence times are often unknown or imprecise. Therefore, we propose a temporal model that assigns a time interval to each event to represent all of its possible occurrence times and revisit pattern evaluation under this model. In particular, we propose the formal semantics of such pattern evaluation, two evaluation frameworks, and algorithms and optimizations in these frameworks. Our evaluation results using both real traces and synthetic systems show that the event-based framework always outperforms the point-based framework and with optimizations, it achieves high efficiency for a wide range of workloads tested.
- J. Agrawal, Y. Diao, et al. Efficient pattern matching over event streams. In SIGMOD, 147--160, 2008. Google Scholar
Digital Library
- M. Akdere, U. Çetintemel, et al. Plan-based complex event detection across distributed sources. PVLDB, 1(1):66--77, 2008. Google ScholarDigital Library
- M. H. Ali, C. Gerea, et al. Microsoft cep server and online behavioral targeting. PVLDB, 2(2):1558--1561, 2009. Google ScholarDigital Library
- R. S. Barga, J. Goldstein, et al. Consistent streaming through time: A vision for event stream processing. In CIDR, 363--374, 2007.Google Scholar
- P. Barham, A. Donnelly, et al. Using Magpie for request extraction and workload modelling. In OSDI, 259--272, 2004. Google ScholarDigital Library
- M. H. Bhlen and C. S. Jensen. Temporal data model and query language concepts. Encyclopedia of Information Systems, 2003.Google ScholarCross Ref
- N. N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. VLDB J., 16(4):523--544, 2007. Google ScholarDigital Library
- A. J. Demers, J. Gehrke, et al. Cayuga: A general purpose event monitoring system. In CIDR, 412--422, 2007.Google Scholar
- L. Ding, S. Chen, et al. Runtime semantic query optimization for event stream processing. In ICDE, 676--685, 2008. Google ScholarDigital Library
- C. E. Dyreson and R. T. Snodgrass. Supporting valid-time indeterminacy. ACM Trans. Database Syst., 23(1):1--57, 1998. Google ScholarDigital Library
- Ganglia monitoring tool. http://ganglia.sourceforge.net/.Google Scholar
- E. Koskinen and J. Jannotti. Borderpatrol: isolating events for black-box tracing. In EuroSys, 191--203, 2008. Google ScholarDigital Library
- M. Liu, M. Li, et al. Sequence pattern query processing over out-of-order event streams. In ICDE, 784--795, 2009. Google ScholarDigital Library
- E. Lo, B. Kao, et al. OLAP on sequence data. In SIGMOD, 649--660, 2008. Google ScholarDigital Library
- Y. Mei and S. Madden. ZStream: a cost-based query processor for adaptively detecting composite events. In SIGMOD, 193--206, 2009. Google ScholarDigital Library
- C. Ré, J. Letchner, et al. Event queries on correlated probabilistic streams. In SIGMOD, 715--728, 2008. Google ScholarDigital Library
- R. Sadri, et al. Expressing and optimizing sequence queries in database systems. ACM Trans. Database Syst., 29(2):282--318, 2004. Google ScholarDigital Library
- U. Srivastava and J. Widom. Flexible time management in data stream systems. In PODS, 263--274, 2004. Google ScholarDigital Library
- T. Tran, C. Sutton, et al. Probabilistic inference over RFID streams in mobile environments. In ICDE, 1096--1107, 2009. Google ScholarDigital Library
- P. A. Tucker, D. Maier, et al. Using punctuation schemes to characterize strategies for querying over data streams. IEEE Trans. Knowl. Data Eng., 19(9):1227--1240, 2007. Google ScholarDigital Library
- W. M. White, M. Riedewald, et al. What is "next" in event processing? In PODS, 263--272, 2007. Google ScholarDigital Library
- E. Wu, Y. Diao, et al. High-performance complex event processing over streams. In SIGMOD, 407--418, 2006. Google ScholarDigital Library
- H. Zhang, Y. Diao, et al. Recognizing Patterns in Streams with Imprecise Timestamps UMass Tech Report UM-CS-2010-025, 2010.Google Scholar
Recommendations
Recognizing patterns in streams with imprecise timestamps
Large-scale event systems are becoming increasingly popular in a variety of domains. Event pattern evaluation plays a key role in monitoring applications in these domains. identifies matches of user-defined patterns on high-volume event streams. ...
Refining imprecise spatio-temporal events: a network-based approach
GIR '16: Proceedings of the 10th Workshop on Geographic Information RetrievalEvents as composites of temporal, spatial and actor information are a central object of interest in many information retrieval (IR) scenarios. There are several challenges to such event-centric IR, which range from the detection and extraction of ...
High-performance complex event processing framework to detect event patterns over video streams
Middleware '19: Proceedings of the 20th International Middleware Conference Doctoral SymposiumComplex Event Processing (CEP) is an event processing paradigm capable of detecting patterns over streaming data in real-time. Presently, CEP systems have key challenges to preform matching over video streams due to their unstructured data model and ...
Comments