Recognizing patterns in streams with imprecise timestamps
Authors:
Open Access
- 1 September 2010
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 3 (1-2) , 244-255
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.Keywords
This publication has 18 references indexed in Scilit:
- Microsoft CEP server and online behavioral targetingProceedings of the VLDB Endowment, 2009
- Plan-based complex event detection across distributed sourcesProceedings of the VLDB Endowment, 2008
- Event queries on correlated probabilistic streams2008
- OLAP on sequence data2008
- Efficient pattern matching over event streams2008
- What is "next" in event processing?2007
- Efficient query evaluation on probabilistic databasesThe VLDB Journal, 2006
- Expressing and optimizing sequence queries in database systemsACM Transactions on Database Systems, 2004
- Temporal Data Model and Query Language Concepts2003
- Supporting valid-time indeterminacyACM Transactions on Database Systems, 1998