High-performance complex event processing over streams

ABSTRACT

In this paper, we present the design, implementation, and evaluation of a system that executes complex event queries over real-time streams of RFID readings encoded as events. These complex event queries filter and correlate events to match specific patterns, and transform the relevant events into new composite events for the use of external monitoring applications. Stream-based execution of these queries enables time-critical actions to be taken in environments such as supply chain management, surveillance and facility management, healthcare, etc. We first propose a complex event language that significantly extends existing event languages to meet the needs of a range of RFID-enabled monitoring applications. We then describe a query plan-based approach to efficiently implementing this language. Our approach uses native operators to efficiently handle query-defined sequences, which are a key component of complex event processing, and pipeline such sequences to subsequent operators that are built by leveraging relational techniques. We also develop a large suite of optimization techniques to address challenges such as large sliding windows and intermediate result sizes. We demonstrate the effectiveness of our approach through a detailed performance analysis of our prototype implementation under a range of data and query workloads as well as through a comparison to a state-of-the-art stream processor.

REFERENCES

• 1: 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]
• 2: Arasu, A., Babu, S., and Widom, J. CQL: A language for continuous queries over streams and relations. In DBPL, 1--19, 2003.
• 3: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 4: U. Dayal , B. Blaustein , A. Buchmann , U. Chakravarthy , M. Hsu , R. Ledin , D. McCarthy , A. Rosenthal , S. Sarin , M. J. Carey , M. Livny , R. Jauhari, The HiPAC project: combining active databases and timing constraints, ACM SIGMOD Record, v.17 n.1, p.51-70, March, 1988 [doi>10.1145/44203.44208]
• 5: Antonio Carzaniga , Alexander L. Wolf, Forwarding in a content-based network, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863975]
• 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: Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M.J., Hellerstein, J.M., Hong, W., et al. TelegraphCQ: Continuous dataflow processing for an uncertain world. In CIDR, 2003.
• 8: Chandy, K.M., Aydemir, B.E., Karpilovsky, E.M., et al. Event webs for crisis management. In Proc. of the 2nd IASTED Int'l Conf. on Communications, Internet and Information Technology, 2003.
• 9: Cherniack, M., Balakrishnan, H., Balazinska, M., Carney, D., et al. Scalable distributed stream processing. In CIDR, 2003.
• 10: Demers, A., Gehrke, J., Hong, M., Riedewald, M., et al. Towards expressive publish/subscribe systems. In EDBT, 627--644, 2006.
• 11: Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003 [doi>10.1145/958942.958947]
• 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: Franklin, M.J., Jeffery, S., Krishnamurthy, S., Reiss, F., Rizvi, S., Wu, E., Cooper, O., Edakkunni, A., and Hong, W. Design considerations for high fan-in systems: The HiFi approach. In CIDR, 2005.
• 14: Simson Garfinkel , Beth Rosenberg, RFID: Applications, Security, and Privacy, Addison-Wesley Professional, 2005
• 15: Gatziu, S and Dittrich, K.R. Events in an active object-oriented database system. In Proc of the 1st Int'l Conference on Rules in Database Systems, 23--39, 1993.
• 16: 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
• 17: Antony Galton , Juan Carlos Augusto, Two Approaches to Event Definition, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.547-556, September 02-06, 2002
• 18: Hinze, A. Efficient filtering of composite events. In Proc. of the British National Database Conference, 207--225, 2003.
• 19: iSpheres. iSpheres EPL server/05 event processing language guide. http://www.ispheres.com.
• 20: Lerner, A. and Shasha, D. AQuery: Query language for ordered data, optimization techniques, and experiments. In VLDB, 345--356, 2003.
• 21: 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
• 22: 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
• 23: C. Michel , Ludovic Mé, ADeLe: An Attack Description Language for Knowledge-Based Intrusion Detection, Proceedings of the IFIP TC11 Sixteenth Annual Working Conference on Information Security: Trusted Information: The New Decade Challenge, p.353-368, June 11-13, 2001
• 24: Motwani, R., Widom, J., Arasu, A., Babcock, B., Babu, S., Datar, M., et al. Query processing, approximation, and resource management in a data stream management system. In CIDR, 2003.
• 25: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States
• 26: 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]
• 27: 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]
• 28: 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
• 29: 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
• 30: 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
          Subjects: Query processing

General Terms:
Algorithms, Design, Languages, Management, Performance

Keywords:
RFID, complex event language, events, query optimization, sequences, streams