High-performance complex event processing using continuous sliding views

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.

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Information systems

  • Data management systems

    • Database management system engines

  • Information systems applications

• Networks

  • Network performance evaluation