Efficient pattern matching over event streams

ABSTRACT

Pattern matching over event streams is increasingly being employed in many areas including financial services, RFIDbased inventory management, click stream analysis, and electronic health systems. While regular expression matching is well studied, pattern matching over streams presents two new challenges: Languages for pattern matching over streams are significantly richer than languages for regular expression matching. Furthermore, efficient evaluation of these pattern queries over streams requires new algorithms and optimizations: the conventional wisdom for stream query processing (i.e., using selection-join-aggregation) is inadequate.

In this paper, we present a formal evaluation model that offers precise semantics for this new class of queries and a query evaluation framework permitting optimizations in a principled way. We further analyze the runtime complexity of query evaluation using this model and develop a suite of techniques that improve runtime efficiency by exploiting sharing in storage and processing. Our experimental results provide insights into the various factors on runtime performance and demonstrate the significant performance gains of our sharing techniques.

REFERENCES

• 1: J. Agrawal, Y. Diao, et al. Efficient pattern matching over event streams. Technical Report 07-63, University of Massachusetts Amherst, 2007.
• 2: Marcos K. Aguilera , Robert E. Strom , Daniel C. Sturman , Mark Astley , Tushar D. Chandra, Matching events in a content-based subscription system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.53-61, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301326]
• 3: A. Arasu, S. Babu, et al. CQL: A language for continuous queries over streams and relations. In DBPL, 1--19, 2003.
• 4: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 5: R. S. Barga, J. Goldstein, et al. Consistent streaming through time: A vision for event stream processing. In CIDR, 363--374, 2007.
• 6: Sharma Chakravarthy , V. Krishnaprasad , Eman Anwar , S.-K. Kim, Composite Events for Active Databases: Semantics, Contexts and Detection, Proceedings of the 20th International Conference on Very Large Data Bases, p.606-617, September 12-15, 1994
• 7: S. Chandrasekaran, O. Cooper, et al. TelegraphCQ: Continuous dataflow processing for an uncertain world. In CIDR, 2003.
• 8: M. Cherniack, H. Balakrishnan, et al. Scalable distributed stream processing. In CIDR, 2003.
• 9: Coral8. http://www.coral8.com/.
• 10: A. J. Demers, J. Gehrke, et al. Towards expressive publish/subscribe systems. In EDBT, 627--644, 2006.
• 11: A. J. Demers, J. Gehrke, et al. Cayuga: A general purpose event monitoring system. In CIDR, 2007.
• 12: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 13: S. Gatziu and K. R. Dittrich. Events in an active object-oriented database system. In Rules in Database Systems, 23--39, 1993.
• 14: Narain H. Gehani , H. V. Jagadish , Oded Shmueli, Composite Event Specification in Active Databases: Model & Implementation, Proceedings of the 18th International Conference on Very Large Data Bases, p.327-338, August 23-27, 1992
• 15: D. Gyllstrom, J. Agrawal, et al. On supporting kleene closure over event streams. In ICDE, 2008. Poster.
• 16: Lilian Harada , Yuuji Hotta, Order checking in a CPOE using event analyzer, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099700]
• 17: John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 18: N. Immerman. Descriptive Complexity. Graduate Texts in Computer Science. Springer, New York, 1999.
• 19: Sailesh Kumar , Balakrishnan Chandrasekaran , Jonathan Turner , George Varghese, Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA [doi>10.1145/1323548.1323574]
• 20: Ming Li , Mo Liu , Luping Ding , Elke A. Rundensteiner , Murali Mani, Event Stream Processing with Out-of-Order Data Arrival, Proceedings of the 27th International Conference on Distributed Computing Systems Workshops, p.67, June 22-29, 2007 [doi>10.1109/ICDCSW.2007.35]
• 21: Leonid Libkin , Limsoon Wong, Unary Quantifiers, Transitive Closure, and Relations of Large Degree, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.183-193, February 25-27, 1998
• 22: Daniel F. Lieuwen , Narain H. Gehani , Robert M. Arlein, The Ode Active Database: Trigger Semantics and Implementation, Proceedings of the Twelfth International Conference on Data Engineering, p.412-420, February 26-March 01, 1996
• 23: Rosa Meo , Giuseppe Psaila , Stefano Ceri, Composite Events in Chimera, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.56-76, March 25-29, 1996
• 24: R. Motwani, J. Widom, et al. Query processing, approximation, and resource management in a data stream management system. In CIDR, 2003.
• 25: Shariq Rizvi , Shawn R. Jeffery , Sailesh Krishnamurthy , Michael J. Franklin , Nathan Burkhart , Anil Edakkunni , Linus Liang, Events on the edge, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066275]
• 26: Reza Sadri , Carlo Zaniolo , Amir Zarkesh , Jafar Adibi, Expressing and optimizing sequence queries in database systems, ACM Transactions on Database Systems (TODS), v.29 n.2, p.282-318, June 2004 [doi>10.1145/1005566.1005568]
• 27: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, The Design and Implementation of a Sequence Database System, Proceedings of the 22th International Conference on Very Large Data Bases, p.99-110, September 03-06, 1996
• 28: Pattern matching in sequences of rows. SQL change proposal. http://asktom.oracle.com/tkyte/row-pattern-recogniton-11-public.pdf. 2007.
• 29: StreamBase. http://www.streambase.com/.
• 30: Truviso. http://www.truviso.com/.
• 31: Fusheng Wang , Peiya Liu, Temporal management of RFID data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 32: Branching programs and binary decision diagrams: theory and applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 33: Walker White , Mirek Riedewald , Johannes Gehrke , Alan Demers, What is "next" in event processing?, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265567]
• 34: Eugene Wu , Yanlei Diao , Shariq Rizvi, High-performance complex event processing over streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142520]
• 35: Fang Yu , Zhifeng Chen , Yanlei Diao , T. V. Lakshman , Randy H. Katz, Fast and memory-efficient regular expression matching for deep packet inspection, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA [doi>10.1145/1185347.1185360]
• 36: D. Zimmer, On the Semantics of Complex Events in Active Database Management Systems, Proceedings of the 15th International Conference on Data Engineering, p.392, March 23-26, 1999

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
event streams, pattern matching, query optimization