skip to main content
10.1145/1619258.1619263acmconferencesArticle/Chapter ViewAbstractPublication PagesdebsConference Proceedingsconference-collections
research-article

Distributed event stream processing with non-deterministic finite automata

Published: 06 July 2009 Publication History

Abstract

Efficient matching of incoming events to persistent queries is fundamental to event pattern matching, complex event processing, and publish/subscribe systems. Recent processing engines based on non-deterministic finite automata (NFAs) have demonstrated scalability in the number of queries that can be efficiently executed on a single machine. However, existing NFA based systems are limited to processing events on a single machine. Consequently, their event processing capacity cannot be increased by adding more machines.
In this paper, we present an experimental evaluation of different methods for distributing an event processing system that is based on NFAs across multiple machines in a cluster. Our results show that careful input stream partitioning gives close to linear performance scaleup for CPU bound workloads.

References

[1]
D. J. Abadi, Y. Ahmad, M. Balazinska, U. Çetintemel, M. Cherniack, J.-H. Hwang, W. Lindner, A. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. B. Zdonik. The design of the borealis stream processing engine. In CIDR, pages 277--289, 2005.
[2]
J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. Efficient pattern matching over event streams. In Proceedings of the 2008 ACM SIGMOD, pages 147--160, New York, NY, USA, 2008. ACM.
[3]
M. Akdere, U. Çetintemel, and N. Tatbul. Plan-based complex event detection across distributed sources. Proc. VLDB Endow., 1(1):66--77, 2008.
[4]
L. Amini, H. Andrade, R. Bhagwan, F. Eskesen, R. King, P. Selo, Y. Park, and C. Venkatramani. Spc: a distributed, scalable platform for data mining. In Proc. of DMSSP '06, pages 27--37, New York, NY, USA, 2006. ACM.
[5]
Y. Amir, C. Danilov, and J. R. Stanton. A low latency, loss tolerant architecture and protocol for wide area group communication. In Proceedings of DSN '00, pages 327--336, Washington, DC, USA, 2000. IEEE Computer Society.
[6]
A. Arasu, M. Cherniack, E. Galvez, D. Maier, A. S. Maskey, E. Ryvkina, M. Stonebraker, and R. Tibbetts. Linear road: a stream data management benchmark. In Proc. of VLDB '04, pages 480--491. VLDB Endowment, 2004.
[7]
M. Balazinska, H. Balakrishnan, and M. Stonebraker. Contract-based load management in federated distributed systems. In Proceedings of NSDI'04, pages 15--15, Berkeley, CA, USA, 2004. USENIX Association.
[8]
Cayuga System (Accessed 11/2008). http://www.cs.cornell.edu/bigreddata/cayuga/.
[9]
M. Cherniack, H. Balakrishnan, M. Balazinska, D. Carney, U. Cetintemel, Y. Xing, and S. Zdonik. Scalable distributed stream processing. In CIDR'03, Asilomar, California, 2003.
[10]
C. Cranor, T. Johnson, O. Spataschek, and V. Shkapenyuk. Gigascope: a stream database for network applications. In Proc. of SIGMOD, pages 647--651, New York, NY, USA, 2003. ACM.
[11]
A. J. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. M. White. Towards expressive publish/subscribe systems. In Proc. of EDBT, pages 627--644, 2006.
[12]
A. J. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and W. M. White. Cayuga: A general purpose event monitoring system. In CIDR, pages 412--422, 2007.
[13]
D. DeWitt and J. Gray. Parallel database systems: the future of high performance database systems. Commun. ACM, 35(6):85--98, 1992.
[14]
F. Fabret, H.-A. Jacobsen, F. Llirbat, J. Pereira, K. A. Ross, and D. Shasha. Filtering algorithms and implementation for very fast publish/subscribe. In Proc. SIGMOD, pages 115--126, 2001.
[15]
R. Friedman and E. Hadad. Adaptive batching for replicated servers. In Proc. of SRDS '06, pages 311--320, Washington, DC, USA, 2006. IEEE Computer Society.
[16]
B. Gedik, H. Andrade, K.-L. Wu, P. S. Yu, and M. Doo. Spade: the systems declarative stream processing engine. In Proceedings of the 2008 ACM SIGMOD, pages 1123--1134, New York, NY, USA, 2008. ACM.
[17]
J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, Second Edition. Addison Wesley, 2000. 2nd edition.
[18]
T. Johnson, M. S. Muthukrishnan, V. Shkapenyuk, and O. Spatscheck. Query-aware partitioning for monitoring massive network data streams. In Proc. of the 2008 ACM SIGMOD, pages 1135--1146, New York, NY, USA, 2008.
[19]
T. Johnson, S. Muthukrishnan, V. Shkapenyuk, and O. Spatscheck. A heartbeat mechanism and its application in Gigascope. In Proc. of VLDB '05, pages 1079--1088, 2005.
[20]
M. Li, M. Liu, L. Ding, E. A. Rundensteiner, and M. Mani. Event stream processing with out-of-order data arrival. In In Proc. of ICDCS '07 Workshops, page 67, Washington, DC, USA, 2007. IEEE Computer Society.
[21]
NASDAQ Performance Statistics (Accessed 11/2008). http://www.nasdaqtrader.com/trader.aspx?id=marketshare.
[22]
C. Olston, J. Jiang, and J. Widom. Adaptive filters for continuous queries over distributed data streams. In Proceedings of the 2003 ACM SIGMOD, pages 563--574, New York, NY, USA, 2003. ACM.
[23]
P. R. Pietzuch, B. Shand, and J. Bacon. A framework for event composition in distributed systems. In Proc. of the 2003 Intl. Conf. on Middleware, pages 62--82, New York, NY, USA, 2003. Springer-Verlag New York, Inc.
[24]
M. A. Shah, J. M. Hellerstein, and E. Brewer. Highly available, fault-tolerant, parallel dataflows. In Proc. of the ACM SIGMOD, pages 827--838, New York, NY, USA, 2004.
[25]
Spread Concepts LLC (Accessed 11/2008). http://www.spread.org.
[26]
U. Srivastava and J. Widom. Flexible time management in data stream systems. In Proc. of PODS '04, pages 263--274, New York, NY, USA, 2004. ACM.
[27]
A. S. Tanenbaum and M. van Steen. Distributed Systems: Principles and Paradigms (2nd Edition), chapter 13, pages 603--607. Prentice-Hall, Inc. NJ, USA, 2006.
[28]
W. White, M. Riedewald, J. Gehrke, and A. Demers. What is "next" in event processing? In Proc. of PODS '07, pages 263--272, New York, NY, USA, 2007. ACM.

Cited By

View all
  • (2024)DecoPa: Query Decomposition for Parallel Complex Event ProcessingProceedings of the ACM on Management of Data10.1145/36549352:3(1-26)Online publication date: 30-May-2024
  • (2023)Formal Verification for Event Stream Processing: Model Checking of BeepBeep Stream Processing PipelinesInformation and Computation10.1016/j.ic.2023.105058(105058)Online publication date: May-2023
  • (2022)DynamAP: Architectural Support for Dynamic Graph Traversal on the Automata ProcessorACM Transactions on Architecture and Code Optimization10.1145/355697619:4(1-26)Online publication date: 7-Oct-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
DEBS '09: Proceedings of the Third ACM International Conference on Distributed Event-Based Systems
July 2009
292 pages
ISBN:9781605586656
DOI:10.1145/1619258
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. NFA
  2. continuous queries
  3. event streams
  4. publish-subscribe

Qualifiers

  • Research-article

Conference

DEBS '09

Acceptance Rates

Overall Acceptance Rate 145 of 583 submissions, 25%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)18
  • Downloads (Last 6 weeks)4
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)DecoPa: Query Decomposition for Parallel Complex Event ProcessingProceedings of the ACM on Management of Data10.1145/36549352:3(1-26)Online publication date: 30-May-2024
  • (2023)Formal Verification for Event Stream Processing: Model Checking of BeepBeep Stream Processing PipelinesInformation and Computation10.1016/j.ic.2023.105058(105058)Online publication date: May-2023
  • (2022)DynamAP: Architectural Support for Dynamic Graph Traversal on the Automata ProcessorACM Transactions on Architecture and Code Optimization10.1145/355697619:4(1-26)Online publication date: 7-Oct-2022
  • (2021)STHITHIKA: Distributed Complex Event Processing with Query Rewriting2021 Moratuwa Engineering Research Conference (MERCon)10.1109/MERCon52712.2021.9525778(705-710)Online publication date: 27-Jul-2021
  • (2020)Massive scale-out of expensive continuous queriesProceedings of the VLDB Endowment10.14778/3402707.34027524:11(1181-1188)Online publication date: 3-Jun-2020
  • (2019)Electric Device Recognition and Recommendation in Real-Time Based on Complex Event Processing for Smart HomesProceedings of the 5th EAI International Conference on Smart Objects and Technologies for Social Good10.1145/3342428.3343033(43-48)Online publication date: 25-Sep-2019
  • (2019)A Comprehensive Survey on Parallelization and Elasticity in Stream ProcessingACM Computing Surveys10.1145/330384952:2(1-37)Online publication date: 30-Apr-2019
  • (2019)Predictive Analytics for Event Stream Processing2019 IEEE 23rd International Enterprise Distributed Object Computing Conference (EDOC)10.1109/EDOC.2019.00029(171-182)Online publication date: Oct-2019
  • (2019)Complex event recognition in the Big Data era: a surveyThe VLDB Journal10.1007/s00778-019-00557-wOnline publication date: 25-Jul-2019
  • (2019)Towards the Identification of Context in 5G InfrastructuresIntelligent Computing10.1007/978-3-030-22868-2_31(406-418)Online publication date: 9-Jul-2019
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media