research-article

Processing nested complex sequence pattern queries over event streams

Authors:

Elke A. Rundensteiner,

Daniel J. Dougherty,

Abhay MehtaAuthors Info & Claims

DMSN '10: Proceedings of the Seventh International Workshop on Data Management for Sensor Networks

Pages 14 - 19

https://doi.org/10.1145/1858158.1858164

Published: 13 September 2010 Publication History

Abstract

Complex event processing (CEP) has become increasingly important for tracking and monitoring applications ranging from health care, supply chain management to surveillance. These monitoring applications submit complex event queries to track sequences of events that match a given pattern. As these systems mature the need for increasingly complex nested sequence queries arises, while the state-of-the-art CEP systems mostly focus on the execution of flat sequence queries only. In this paper, we now introduce an iterative execution strategy for nested CEP queries composed of sequence, negation, AND and OR operators. Lastly we have introduced the promising direction of applying selective caching of intermediate results to optimize the execution. Our experimental study using real-world stock trades evaluates the performance of our proposed iterative execution strategy for different query types.

References

[1]

}}E. Wu, Y. Diao, and S. Rizvi, "High-performance complex event processing over streams." in SIGMOD Conference, 2006, pp. 407--418.

Digital Library

[2]

}}A. J. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and W. M. White, "Cayuga: A general purpose event monitoring system." in CIDR, 2007, pp. 412--422.

[3]

}}Y. Mei and S. Madden, "Zstream: a cost-based query processor for adaptively detecting composite events," in SIGMOD Conference, 2009, pp. 193--206.

Digital Library

[4]

}}J. M. Boyce and D. Pittet, "Guideline for hand hygiene in healthcare settings," MMWR Recomm Rep., vol. 51, pp. 1--45, 2002.

[5]

}}C. R. Baker and et al., "Wireless sensor networks for home health care."

[6]

}}R. S. Barga, J. Goldstein, M. Ali, and M. Hong, "Consistent streaming through time: A vision for event stream processing." in CIDR, 2007, pp. 363--374.

[7]

}}M. Liu, E. Rundensteiner, D. Dougherty, C. Gupta, S. Wang, and A. Mehta, "Neel: The nested complex event language for real-time event analytics," in BIRTE, 2010, pp. 358--369.

[8]

}}S. Chakravarthy, V. Krishnaprasad, E. Anwar, and S.-K. Kim, "Composite events for active databases: Semantics, contexts and detection." in VLDB, 1994, pp. 606--617.

Digital Library

[9]

}}A. J. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and W. M. White, "Cayuga: A general purpose event monitoring system." in CIDR, 2007, pp. 412--422.

[10]

}}J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman, "Efficient pattern matching over event streams," in SIGMOD Conference, 2008, pp. 147--160.

Digital Library

[11]

}}D. Gyllstrom, J. Agrawal, Y. Diao, and N. Immerman, "On supporting kleene closure over event streams," in ICDE, 2008, pp. 1391--1393.

Digital Library

[12]

}}P. Seshadri, H. Pirahesh, and T. Y. C. Leung, "Complex query decorrelation," in ICDE, 1996, pp. 450--458.

Digital Library

[13]

}}I. S. Mumick, S. J. Finkelstein, H. Pirahesh, and R. Ramakrishnan, "Magic is relevant," in SIGMOD Conference, 1990, pp. 247--258.

Digital Library

[14]

}}E. Wong and K. Youssefi, "Decomposition - a strategy for query processing," ACM Trans. Database Syst., vol. 1, no. 3, pp. 223--241, 1976.

Digital Library

[15]

}}J. M. Smith and P. Y.-T. Chang, "Optimizing the performance of a relational algebra database interface," Commun. ACM, vol. 18, no. 10, pp. 568--579, 1975.

Digital Library

[16]

}}M. Liu, E. A. Rundensteiner, K. Greenfield, C. Gupta, S. Wang, I. Ari, and A. Mehta, "E-cube: Multi-dimensional event sequence processing using concept and pattern hierarchies," in ICDE, 2010, pp. 1097--1100.

[17]

}}"I. inetats. stock trade traces. http://www.inetats.com/."

[18]

}}P. Seshadri, H. Pirahesh, and T. Y. C. Leung, "Complex query decorrelation," in ICDE '96: Proceedings of the Twelfth International Conference on Data Engineering. IEEE Computer Society, 1996, pp. 450--458.

Digital Library

[19]

}}U. Dayal, "Of nests and trees: A unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers," in VLDB, 1987, pp. 197--208.

Digital Library

[20]

}}J. Shim, P. Scheuermann, and R. Vingralek, "Dynamic caching of query results for decision support systems," in SSDBM, 1999, pp. 254--263.

Digital Library

[21]

}}S. Dar, M. J. Franklin, B. T. Jónsson, D. Srivastava, and M. Tan, "Semantic data caching and replacement," in VLDB, 1996, pp. 330--341.

Digital Library

[22]

}}L. Chen and E. A. Rundensteiner, "Xquery containment in presence of variable binding dependencies," in WWW, 2005, pp. 288--297.

Digital Library

[23]

}}L. Chen, E. Rundensteiner, and S. Wang, "Xcache: A semantic caching system for xml queries," in ACM SIGMOD, 2002, pp. 618--618.

Digital Library

Cited By

Perera KAhangama S(2019)A Review of Query Optimization Techniques for Complex Event Processing2019 4th International Conference on Information Technology Research (ICITR)10.1109/ICITR49409.2019.9407794(1-7)Online publication date: 10-Dec-2019
https://doi.org/10.1109/ICITR49409.2019.9407794
Peng SHe J(2016)Efficient Context-Aware Nested Complex Event Processing over RFID StreamsWeb-Age Information Management10.1007/978-3-319-47121-1_11(125-136)Online publication date: 15-Oct-2016
https://doi.org/10.1007/978-3-319-47121-1_11
Leghari AWolf MZhou Y(2015)Efficient Pattern Detection Over a Distributed FrameworkEnabling Real-Time Business Intelligence10.1007/978-3-662-46839-5_9(133-149)Online publication date: 30-Apr-2015
https://doi.org/10.1007/978-3-662-46839-5_9
Show More Cited By

Index Terms

Processing nested complex sequence pattern queries over event streams
1. Information systems
  1. Information systems applications

Recommendations

High-performance complex event processing over streams
SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of data

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 ...
Nested Pattern Queries Processing Optimization over Multi-dimensional Event Streams
COMPSAC '13: Proceedings of the 2013 IEEE 37th Annual Computer Software and Applications Conference

Recently, many modern applications have required complex event processing technology to analyze multi-dimensional stream big data available in real-time data feeds. To address the above requirement, we develop a novel real-time event stream processing ...
Optimization of complex nested queries in relational databases

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

DMSN '10: Proceedings of the Seventh International Workshop on Data Management for Sensor Networks

September 2010

45 pages

ISBN:9781450304160

DOI:10.1145/1858158

Conference Chairs:
Demetris Zeinalipour
University of Cyprus, Nicosia, Cypru
,
Wang-Chien Lee
The Pennsylvania State University, University Park, PA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

CONET

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 September 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

DMSN '10

Sponsor:

DMSN '10: 7th International Workshop on Data Management for Sensor Networks

September 13, 2010

Singapore

Acceptance Rates

Overall Acceptance Rate 6 of 16 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
258
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Perera KAhangama S(2019)A Review of Query Optimization Techniques for Complex Event Processing2019 4th International Conference on Information Technology Research (ICITR)10.1109/ICITR49409.2019.9407794(1-7)Online publication date: 10-Dec-2019
https://doi.org/10.1109/ICITR49409.2019.9407794
Peng SHe J(2016)Efficient Context-Aware Nested Complex Event Processing over RFID StreamsWeb-Age Information Management10.1007/978-3-319-47121-1_11(125-136)Online publication date: 15-Oct-2016
https://doi.org/10.1007/978-3-319-47121-1_11
Leghari AWolf MZhou Y(2015)Efficient Pattern Detection Over a Distributed FrameworkEnabling Real-Time Business Intelligence10.1007/978-3-662-46839-5_9(133-149)Online publication date: 30-Apr-2015
https://doi.org/10.1007/978-3-662-46839-5_9
Wang KYu Y(2013)A query-matching mechanism over out-of-order event stream in IOTInternational Journal of Ad Hoc and Ubiquitous Computing10.1504/IJAHUC.2013.05545313:3/4(197-208)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1504/IJAHUC.2013.055453
Ray MRundensteiner ELiu MGupta CWang SAri IGuerrini GPaton N(2013)High-performance complex event processing using continuous sliding viewsProceedings of the 16th International Conference on Extending Database Technology10.1145/2452376.2452437(525-536)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2452376.2452437
Liu MRay MZhang DRundensteiner EDougherty DGupta CWang SAri I(2012)Realtime healthcare services via nested complex event processing technologyProceedings of the 15th International Conference on Extending Database Technology10.1145/2247596.2247681(622-625)Online publication date: 27-Mar-2012
https://dl.acm.org/doi/10.1145/2247596.2247681
Cho EHelal S(2011)A Situation-Based Exception Detection Mechanism for Safety in Pervasive SystemsProceedings of the 2011 IEEE/IPSJ International Symposium on Applications and the Internet10.1109/SAINT.2011.35(196-201)Online publication date: 18-Jul-2011
https://dl.acm.org/doi/10.1109/SAINT.2011.35
Ray MLiu MRundensteiner EDougherty DGupta CWang SMehta AAri I(2011)Optimizing complex sequence pattern extraction using cachingProceedings of the 2011 IEEE 27th International Conference on Data Engineering Workshops10.1109/ICDEW.2011.5767641(243-248)Online publication date: 11-Apr-2011
https://dl.acm.org/doi/10.1109/ICDEW.2011.5767641
Liu MRundensteiner EDougherty DGupta CWang SAri IMehta A(2011)High-performance nested CEP query processing over event streamsProceedings of the 2011 IEEE 27th International Conference on Data Engineering10.1109/ICDE.2011.5767839(123-134)Online publication date: 11-Apr-2011
https://dl.acm.org/doi/10.1109/ICDE.2011.5767839
Liu MRundensteiner EDougherty DGupta CWang SAri IMehta A(2011)NEEL: The Nested Complex Event Language for Real-Time Event AnalyticsEnabling Real-Time Business Intelligence10.1007/978-3-642-22970-1_9(116-132)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22970-1_9

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents