[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2452376.2452437acmotherconferencesArticle/Chapter ViewAbstractPublication PagesedbtConference Proceedingsconference-collections
research-article

High-performance complex event processing using continuous sliding views

Published: 18 March 2013 Publication History

Abstract

Complex Event Processing (CEP) has become increasingly important for tracking and monitoring anomalies and trends in event streams emitted from business processes such as supply chain management to online stores in e-commerce. These monitoring applications submit complex event queries to track sequences of events that match a given pattern. While the state-of-the-art CEP systems mostly focus on the execution of flat sequence queries, we instead support the execution of nested CEP queries specified by the (NEsted Event Language) NEEL. However the iterative execution often results in the repeated recomputation of similar or even identical results for nested subexpressions as the window slides over the event stream. In this work we thus propose to optimize NEEL execution performance by caching intermediate results. In particular we design two methods of applying selective caching of intermediate results. The first is the Continuous Sliding Caching technique. The second is a further optimization of the previous technique which we call the Interval-Driven Semantic Caching. Techniques for incrementally loading, purging and exploiting the cache content are described. Our experimental study using real-world stock trades evaluates the performance of our proposed caching strategies for different query types.

References

[1]
E. Wu, Y. Diao, and S. Rizvi, "High-performance complex event processing over streams." in SIGMOD, 2006, pp. 407--418.
[2]
A. J. Demers et al., "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, 2009, pp. 193--206.
[4]
M. Liu, E. A. Rundensteiner, D. J. Dougherty, C. Gupta, S. Wang, I. Ari, and A. Mehta, "NEEL: The nested complex event language for real-time event analytics," in BIRTE, VLDB WOrkshop, 2010, pp. 116--132.
[5]
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.
[6]
M. Liu, M. Ray, E. A. Rundensteiner, D. J. Dougherty, C. Gupta, S. Wang, I. Ari, and A. Mehta, "Processing nested complex sequence pattern queries over event streams," in DMSN, VLDB Workshop, 2010, pp. 14--19.
[7]
"Esper 2009, http://esper.codehaus.org/. accessed july 2009."
[8]
M. Liu, E. A. Rundensteiner, D. Dougherty, C. Gupta, S. Wang, I. Ari, and A. Mehta, "High-performance nested CEP query processing over event streams," in ICDE, April, 2011.
[9]
W. Kim, "On optimizing an sql-like nested query," ACM Trans. Database Syst., vol. 7, pp. 443--469, 1982.
[10]
P. Seshadri, H. Pirahesh, and T. Y. C. Leung, "Complex query decorrelation," in ICDE, 1996, pp. 450--458.
[11]
Mumick, IS. and Finkelstein, S. and Pirahesh, H. and Ramakrishnan. R, "Magic is relevant." in SIGMOD, 1990.
[12]
A. Kawaguchi, D. Lieuwen, I. Mumick, and K. Ross, "Implementing incremental view maintenance in nested data models," in Database Programming Languages, 1998.
[13]
M. Liu, E. A. Rundensteiner, D. J. Dougherty, C. Gupta, S. Wang, and I. Ari, "E-Cube: Multi-dimensional event sequence analysis using hierarchical pattern query sharing," in SIGMOD, 2011.
[14]
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.
[15]
B. Mozafari, K. Zeng, and C. Zaniolo, "Ik*sql: A unifying engine for sequence patterns and xml."
[16]
S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim, "Optimizing queries with materialized views," in ICDE, 1995.
[17]
L. A. Y., R. A., and O. J. J., "Query answering algorithms for information agents," in Proc. National Conference on Artificial Intelligence, 1996, pp. 270--294.
[18]
P. Seshadri, M. Livny, and R. Ramakrishnan, "Sequence query processing," in SIGMOD, 1994, pp. 430--441.
[19]
F. M. Dar S., J. B., S. D., and T. M., "Semantic data caching and replacement," in VLDB, 1996, pp. 330--341.
[20]
KellerA.M. and B. J., "Apredicate-based caching scheme for client-server database architectures," in VLDB Journal, 1996, pp. 330--341.
[21]
B. Cao and A. Badia, "A nested relational approach to processing sql subqueries," in SIGMOD, 2005, pp. 191--202.
[22]
Dayal, U, "A unified approach to processing queries that contain nested subqueries aggregates and quantifiers." in VLDB, 1987.
[23]
"I. inetats. stock trade traces. http://www.inetats.com/."
[24]
M. A. Nascimento and M. H. Dunham, "Indexing valid time databases via b+-trees," IEEE Trans. on Knowl. and Data Eng., pp. 929--947, 1999.
[25]
B. Gedik and et al., "Adaptive load shedding for windowed stream joins," in CIKM, 2005.
[26]
B. Liu, Y. Zhu, and E. Rundensteiner, "Run-time operator state spilling for memory intensive long-running queries," in SIGMOD, 2006.

Cited By

View all
  • (2022)PLQ: An Efficient Approach to Processing Pattern-Based Log QueriesJournal of Computer Science and Technology10.1007/s11390-020-0653-537:5(1239-1254)Online publication date: 30-Sep-2022
  • (2021)Efficient Complete Event Trend Detection over High-Velocity StreamsProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3472526(1-12)Online publication date: 9-Aug-2021
  • (2019)Real-Time Multi-Pattern Detection over Event StreamsProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319869(589-606)Online publication date: 25-Jun-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences
EDBT '13: Proceedings of the 16th International Conference on Extending Database Technology
March 2013
793 pages
ISBN:9781450315975
DOI:10.1145/2452376
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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 March 2013

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Conference

EDBT/ICDT '13

Acceptance Rates

Overall Acceptance Rate 7 of 10 submissions, 70%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 23 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)PLQ: An Efficient Approach to Processing Pattern-Based Log QueriesJournal of Computer Science and Technology10.1007/s11390-020-0653-537:5(1239-1254)Online publication date: 30-Sep-2022
  • (2021)Efficient Complete Event Trend Detection over High-Velocity StreamsProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3472526(1-12)Online publication date: 9-Aug-2021
  • (2019)Real-Time Multi-Pattern Detection over Event StreamsProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319869(589-606)Online publication date: 25-Jun-2019
  • (2019)Optimization RFID-enabled Retail Store Management with Complex Event ProcessingInternational Journal of Automation and Computing10.1007/s11633-018-1164-516:1(52-64)Online publication date: 1-Feb-2019
  • (2018)Join query optimization techniques for complex event processing applicationsProceedings of the VLDB Endowment10.14778/3236187.323618911:11(1332-1345)Online publication date: 1-Jul-2018
  • (2017)Complete Event Trend Detection in High-Rate Event StreamsProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3035947(109-124)Online publication date: 9-May-2017
  • (2016)SPASSProceedings of the 10th ACM International Conference on Distributed and Event-based Systems10.1145/2933267.2933288(336-339)Online publication date: 13-Jun-2016
  • (2016)Scalable Pattern Sharing on Event Streams*Proceedings of the 2016 International Conference on Management of Data10.1145/2882903.2882947(495-510)Online publication date: 26-Jun-2016
  • (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

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media