research-article

RIP: run-based intra-query parallelism for scalable complex event processing

Authors:

Cagri Balkesen,

Matthias Wetter,

Nesime TatbulAuthors Info & Claims

DEBS '13: Proceedings of the 7th ACM international conference on Distributed event-based systems

Pages 3 - 14

https://doi.org/10.1145/2488222.2488257

Published: 29 June 2013 Publication History

Abstract

Recognition of patterns in event streams has become important in many application areas of Complex Event Processing (CEP) including financial markets, electronic health-care systems, and security monitoring systems. In most applications, patterns have to be detected continuously and in real-time over streams that are generated at very high rates, imposing high-performance requirements on the underlying CEP system. For scaling CEP systems to increasing workloads, parallel pattern matching techniques that can exploit multi-core processing opportunities are needed. In this paper, we propose RIP - a Run-based Intra-query Parallelism technique for scalable pattern matching over event streams. RIP distributes input events that belong to individual run instances of a pattern's Finite State Machine (FSM) to different processing units, thereby providing fine-grained partitioned data parallelism. We compare RIP to a state-based alternative which partitions individual FSM states to different processing units instead. Our experiments demonstrate that RIP's partitioned parallelism approach outperforms the pipelined parallelism approach of this state-based alternative, achieving near-linear scalability that is independent from the query pattern definition.

References

[1]

Day trading technical analysis. http://www.daytradingcoach.com/daytrading-technicalanalysis-course.htm. Accessed: 03/11/2012.

[2]

Esper. http://www.espertech.com. Accessed: 02/12/2012.

[3]

Head and shoulders. http://www.chartpatterns.com/headandshoulders.htm. Accessed: 03/02/2013.

[4]

Head and shoulders (chart pattern). http://en.wikipedia.org/wiki/Head_and_shoulders_(chart_pattern). Accessed: 10/11/2012.

[5]

NYSE DataSolutions. http://www.nyxdata.com/nysedata/.

[6]

Oracle CEP. http://www.oracle.com/technetwork/middleware/complex-event-processing/index.html.

[7]

J. Agrawal et al. Effcient Pattern Matching over Event Streams. In ACM SIGMOD Conference, Vancouver, Canada, 2008.

Digital Library

[8]

L. Brenna et al. Distributed Event Stream Processing with Non-deterministic Finite Automata. In ACM DEBS Conference, Nashville, Tennessee, July 2009.

Digital Library

[9]

G. Cugola et al. Tesla: a formally defined event specification language. In Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems, DEBS '10, pages 50--61, New York, NY, USA, 2010. ACM.

Digital Library

[10]

A. Demers et al. Cayuga: A General Purpose Event Monitoring System. In CIDR Conference, Asilomar, CA, 2007.

[11]

N. Dindar et al. DejaVu: Declarative Pattern Matching over Live and Archived Streams of Events (Demo). In ACM SIGMOD Conference, Providence, RI, 2009.

Digital Library

[12]

N. Dindar et al. Effciently Correlating Complex Events over Live and Archived Data Streams. In ACM International Conference on Distributed Event-Based Systems (DEBS'11), New York, NY, USA, July 2011.

Digital Library

[13]

M. Hirzel. Partition and Compose: Parallel Complex Event Processing. In ACM DEBS Conference, Berlin, Germany, July 2012.

Digital Library

[14]

Y. Mei et al. ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events. In ACM SIGMOD Conference, Providence, RI, June 2009.

Digital Library

[15]

S. Schneider et al. Auto-Parallelizing Stateful Distributed Streaming Applications. In ACM PACT Conference, Minneapolis, MN, September 2012.

Digital Library

[16]

E. Wu et al. High-Performance Complex Event Processing over Streams. In ACM SIGMOD Conference, Chicago, IL, June 2006.

Digital Library

[17]

S. Wu et al. Parallelizing Stateful Operators in a Distributed Stream Processing System: How, Should you and How much? In ACM DEBS Conference, Berlin, Germany, July 2012.

Digital Library

[18]

F. Zemke et al. Pattern Matching in Sequences of Rows. Technical Report ANSI Standard Proposal, 2007.

Cited By

Akili SPurtzel SWeidlich M(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
https://dl.acm.org/doi/10.1145/3654935
Purtzel SAkili SWeidlich M(2024)Efficient multi-query evaluation for distributed CEP through predicate-based push–pull plansInformation Systems10.1016/j.is.2023.102250120:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.is.2023.102250
Akili SPurtzel SWeidlich M(2023)INEv: In-Network Evaluation for Event Stream ProcessingProceedings of the ACM on Management of Data10.1145/35889551:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588955
Show More Cited By

Index Terms

RIP: run-based intra-query parallelism for scalable complex event processing
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Partition and compose: parallel complex event processing
DEBS '12: Proceedings of the 6th ACM International Conference on Distributed Event-Based Systems

Complex event processing uses patterns to detect composite events in streams of simple events. Typically, the events are logically partitioned by some key. For instance, the key can be the stock symbol in stock quotes, the author in tweets, the vehicle ...
Scaling Ordered Stream Processing on Shared-Memory Multicores
BIRTE 2019: Proceedings of Real-Time Business Intelligence and Analytics

Many modern applications require realtime processing of large volumes of high speed data. Such data processing can be specified in the form of a dataflow graph that exposes multiple opportunities for parallelizing its execution, in the form of data, ...
SGTNE: semi-global time of the next event algorithm
PADS '95: Proceedings of the ninth workshop on Parallel and distributed simulation

This paper describes an extension of the TNE algorithm, the objective of which is to increase its parallelism and to break the inter-processor deadlocks inherent with the use of TNE. The algorithm, which we call the SGTNE algorithm (Semi Global TNE), is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DEBS '13: Proceedings of the 7th ACM international conference on Distributed event-based systems

June 2013

360 pages

ISBN:9781450317580

DOI:10.1145/2488222

General Chairs:
Sharma Chakravarthy
The University of Texas at Arlington, USA
,
Susan D. Urban
Texas Tech University, USA
,
Program Chairs:
Peter Pietzuch
Imperial College, UK
,
Elke Rundensteiner
Worcester Polytechnic Institute, USA

Copyright © 2013 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DEBS '13

Sponsor:

DEBS '13: The 7th ACM International Conference on Distributed Event-Based Systems

June 29 - July 3, 2013

Texas, Arlington, USA

Acceptance Rates

DEBS '13 Paper Acceptance Rate 16 of 58 submissions, 28%;

Overall Acceptance Rate 145 of 583 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
411
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Akili SPurtzel SWeidlich M(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
https://dl.acm.org/doi/10.1145/3654935
Purtzel SAkili SWeidlich M(2024)Efficient multi-query evaluation for distributed CEP through predicate-based push–pull plansInformation Systems10.1016/j.is.2023.102250120:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.is.2023.102250
Akili SPurtzel SWeidlich M(2023)INEv: In-Network Evaluation for Event Stream ProcessingProceedings of the ACM on Management of Data10.1145/35889551:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588955
Slo ABhowmik SRothermel K(2023)gSPICE: Model-Based Event Shedding in Complex Event Processing2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386775(263-270)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386775
Kuhrt MKörber MSeeger B(2022)iGPU-Accelerated Pattern Matching on Event StreamsProceedings of the 18th International Workshop on Data Management on New Hardware10.1145/3533737.3535099(1-7)Online publication date: 12-Jun-2022
https://dl.acm.org/doi/10.1145/3533737.3535099
Yankovitch MKolchinsky ISchuster AIves ZBonifati AEl Abbadi A(2022)HYPERSONIC: A Hybrid Parallelization Approach for Scalable Complex Event ProcessingProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517829(1093-1107)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517829
Slo ABhowmik SRothermel K(2022)State-Aware Load Shedding From Input Event Streams in Complex Event ProcessingIEEE Transactions on Big Data10.1109/TBDATA.2020.30474388:5(1340-1357)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TBDATA.2020.3047438
Ntoulias EAlevizos EArtikis AAkasiadis CKoumparos A(2022)Online fleet monitoring with scalable event recognition and forecastingGeoInformatica10.1007/s10707-022-00465-226:4(613-644)Online publication date: 11-May-2022
https://doi.org/10.1007/s10707-022-00465-2
Körber MGlombiewski NSeeger BLi GLi ZIdreos SSrivastava D(2021)Index-Accelerated Pattern Matching in Event StoresProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457245(1023-1036)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457245
Slo ABhowmik SRothermel KGascon-Samson JZhang KDaudjee KKemme B(2020)hSPICEProceedings of the 14th ACM International Conference on Distributed and Event-based Systems10.1145/3401025.3401742(109-120)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.1145/3401025.3401742
Show More Cited By

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