More Web Proxy on the site http://driver.im/

research-article

SPECTRE: supporting consumption policies in window-based parallel complex event processing

Authors:

Muhammad Adnan Tariq,

Kurt Rothermel,

Manuel Gräber,

Umakishore RamachandranAuthors Info & Claims

Middleware '17: Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference

Pages 161 - 173

https://doi.org/10.1145/3135974.3135983

Published: 11 December 2017 Publication History

Abstract

Distributed Complex Event Processing (DCEP) is a paradigm to infer the occurrence of complex situations in the surrounding world from basic events like sensor readings. In doing so, DCEP operators detect event patterns on their incoming event streams. To yield high operator throughput, data parallelization frameworks divide the incoming event streams of an operator into overlapping windows that are processed in parallel by a number of operator instances. In doing so, the basic assumption is that the different windows can be processed independently from each other. However, consumption policies enforce that events can only be part of one pattern instance; then, they are consumed, i.e., removed from further pattern detection. That implies that the constituent events of a pattern instance detected in one window are excluded from all other windows as well, which breaks the data parallelism between different windows. In this paper, we tackle this problem by means of speculation: Based on the likelihood of an event's consumption in a window, subsequent windows may speculatively suppress that event. We propose the SPECTRE framework for speculative processing of multiple dependent windows in parallel. Our evaluations show an up to linear scalability of SPECTRE with the number of CPU cores.

References

[1]

Asaf Adi and Opher Etzion. 2004. Amit - the Situation Manager. The VLDB Journal 13, 2 (May 2004), 177--203.

Digital Library

[2]

Tyler Akidau, Alex Balikov, Kaya Bekiroglu, Slava Chernyak, Josh Haberman, Reuven Lax, Sam McVeety, Daniel Mills, Paul Nordstrom, and Sam Whittle. 2013. MillWheel: Fault-tolerant Stream Processing at Internet Scale. Proc. VLDB Endow. 6, 11 (Aug. 2013), 1033--1044.

Digital Library

[3]

Arvind Arasu, Shivnath Babu, and Jennifer Widom. 2006. The CQL Continuous Query Language: Semantic Foundations and Query Execution. The VLDB Journal 15, 2 (June 2006), 121--142.

Digital Library

[4]

Magdalena Balazinska, YongChul Kwon, Nathan Kuchta, and Dennis Lee. 2007. Moirae: History-Enhanced Monitoring. In CIDR. Citeseer, 375--386.

[5]

Cagri Balkesen, Nihal Dindar, Matthias Wetter, and Nesime Tatbul. 2013. RIP:Run-based intra-query parallelism for scalable complex event processing (DEBS'13). ACM, 3--14.

Digital Library

[6]

Cagri Balkesen and Nesime Tatbul. 2011. Scalable data partitioning techniques for parallel sliding window processing over data streams. In International Workshop on Data Management for Sensor Networks (DMSN).

[7]

Andrey Brito, Christof Fetzer, and Pascal Felber. 2009. Minimizing Latency in Fault-Tolerant Distributed Stream Processing Systems. In 2009 29th IEEE International Conference on Distributed Computing Systems. 173-182.

Digital Library

[8]

Andrey Brito, Christof Fetzer, Heiko Sturzrehm, and Pascal Felber. 2008. Speculative Out-of-order Event Processing with Software Transaction Memory. In Proceedings of the Second International Conference on Distributed Event-based Systems (DEBS '08). ACM, New York, NY, USA, 265--275.

Digital Library

[9]

Raul Castro Fernandez, Matteo Migliavacca, Evangelia Kalyvianaki, and Peter Pietzuch. 2013. Integrating Scale out and Fault Tolerance in Stream Processing Using Operator State Management (SIGMOD '13). ACM, 725--736.

Digital Library

[10]

Sharma Chakravarthy and Deepak Mishra. 1994. Snoop: An expressive event specification language for active databases. Data Knowl. Eng. 14, 1 (1994), 1--26.

Digital Library

[11]

Gianpaolo Cugola and Alessandro Margara. 2010. TESLA: A Formally Defined Event Specification Language. In Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems (DEBS '10). ACM, New York, NY, USA, 50--61.

Digital Library

[12]

Gianpaolo Cugola and Alessandro Margara. 2012. Complex Event Processing with T-REX. J. Syst. Softw. 85, 8 (Aug. 2012), 1709--1728.

Digital Library

[13]

Gianpaolo Cugola and Alessandro Margara. 2012. Low latency complex event processing on parallel hardware. J. Parallel and Distrib. Comput. 72, 2 (2012), 205 -- 218.

Digital Library

[14]

Tiziano De Matteis and Gabriele Mencagli. 2016. Keep Calm and React with Foresight: Strategies for Low-latency and Energy-efficient Elastic Data Stream Processing. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '16). ACM, New York, NY, USA, Article 13, 12 pages.

Digital Library

[15]

Tiziano De Matteis and Gabriele Mencagli. 2017. Parallel Patterns for Window-Based Stateful Operators on Data Streams: An Algorithmic Skeleton Approach. International Journal of Parallel Programming 45, 2 (01 Apr 2017), 382--401.

Digital Library

[16]

Buĝra Gedik. 2014. Partitioning functions for stateful data parallelism in stream processing. The VLDB Journal 23, 4 (2014), 517--539.

Digital Library

[17]

Martin Hirzel. 2012. Partition and Compose: Parallel Complex Event Processing. In Proceedings of the 6th ACM International Conference on Distributed Event-Based Systems (DEBS '12). ACM, New York, NY, USA, 191--200.

Digital Library

[18]

Martin Hirzel, Robert Soulé, Scott Schneider, Buĝra Gedik, and Robert Grimm. 2014. A Catalog of Stream Processing Optimizations. ACM Comput. Surv. 46, 4, Article 46 (March 2014), 34 pages.

Digital Library

[19]

Navendu Jain, Lisa Amini, Henrique Andrade, Richard King, Yoonho Park, Philippe Selo, and Chitra Venkatramani. 2006. Design, Implementation, and Evaluation of the Linear Road Benchmark on the Stream Processing Core (SIGMOD '06). ACM, 431--442.

Digital Library

[20]

Ilya Kolchinsky, Izchak Sharfman, and Assaf Schuster. 2015. Lazy Evaluation Methods for Detecting Complex Events. In Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems (DEBS '15). ACM, New York, NY, USA, 34-45.

Digital Library

[21]

Boris Koldehofe, Ruben Mayer, Umakishore Ramachandran, Kurt Rothermel, and Marco Völz. 2013. Rollback-recovery Without Checkpoints in Distributed Event Processing Systems. In Proceedings of the 7th ACM International Conference on Distributed Event-based Systems (DEBS '13). ACM, New York, NY, USA, 27--38.

Digital Library

[22]

Alexandros Koliousis, Matthias Weidlich, Raul Castro Fernandez, Alexander L. Wolf, Paolo Costa, and Peter Pietzuch. 2016. SABER: Window-Based Hybrid Stream Processing for Heterogeneous Architectures (SIGMOD '16). ACM, 555--569.

Digital Library

[23]

Jin Li, David Maier, Kristin Tufte, Vassilis Papadimos, and Peter A. Tucker. 2005. No Pane, No Gain: Efficient Evaluation of Sliding-window Aggregates over Data Streams. SIGMOD Rec. 34, 1 (March 2005), 39-44.

Digital Library

[24]

Björn Lohrmann, Peter Janacik, and Odej Kao. 2015. Elastic Stream Processing with Latency Guarantees. In 2015 IEEE 35th International Conference on Distributed Computing Systems (ICDCS '15). 399--410.

[25]

Ruben Mayer, Boris Koldehofe, and Kurt Rothermel. 2015. Predictable Low-Latency Event Detection with Parallel Complex Event Processing. Internet of Things Journal, IEEE 2, 4 (Aug 2015), 274--286.

[26]

Ruben Mayer, Christian Mayer, Muhammad Adnan Tariq, and Kurt Rothermel. 2016. GraphCEP: Real-time Data Analytics Using Parallel Complex Event and Graph Processing. In Proceedings of the 10th ACM International Conference on Distributed and Event-based Systems (DEBS '16). ACM, New York, NY, USA, 309316.

Digital Library

[27]

Ruben Mayer, Muhammad Adnan Tariq, and Kurt Rothermel. 2017. Minimizing Communication Overhead in Window-Based Parallel Complex Event Processing. In Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems (DEBS '17). ACM, New York, NY, USA, 54--65.

Digital Library

[28]

Christopher Mutschler and Michael Philippsen. 2014. Adaptive Speculative Processing of Out-of-Order Event Streams. ACM Trans. Internet Technol. 14, 1, Article 4 (Aug. 2014), 24 pages.

Digital Library

[29]

Nicholas Poul Schultz-Møller, Matteo Migliavacca, and Peter Pietzuch. 2009. Distributed Complex Event Processing with Query Rewriting (DEBS '09). ACM, Article 4, 12 pages.

[30]

Benjamin Wester, James Cowling, Edmund B. Nightingale, Peter M. Chen, Jason Flinn, and Barbara Liskov. 2009. Tolerating Latency in Replicated State Machines Through Client Speculation. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09). USENIX Association, Berkeley, CA, USA, 245--260.

Digital Library

[31]

Eugene Wu, Yanlei Diao, and Shariq Rizvi. 2006. High-performance Complex Event Processing over Streams (SIGMOD '06). ACM, 407--418.

Digital Library

[32]

Erik Zeitler and Tore Risch. 2011. Massive scale-out of expensive continuous queries. VLDB Endowment 4, 11 (2011), 1181-1188.

Digital Library

[33]

Fred Zemke, Andrew Witkowski, and Mitch Cherniak. 2007. Pattern matching in sequences of rows. (2007).

[34]

D. Zimmer and R. Unland. 1999. On the semantics of complex events in active database management systems. In Data Engineering, 1999. Proceedings., 15th International Conference on. 392--399.

Digital Library

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
Gulisano VMargara A(2024)Aggregates are all you need (to bridge stream processing and Complex Event Recognition)Proceedings of the 18th ACM International Conference on Distributed and Event-based Systems10.1145/3629104.3666032(66-77)Online publication date: 24-Jun-2024
https://dl.acm.org/doi/10.1145/3629104.3666032
Boughzala BGärtner CKoldehofe BZhou YChrysanthis PGulisano V(2022)Window-based parallel operator execution with in-network computingProceedings of the 16th ACM International Conference on Distributed and Event-Based Systems10.1145/3524860.3539804(91-96)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1145/3524860.3539804
Show More Cited By

Index Terms

SPECTRE: supporting consumption policies in window-based parallel complex event processing
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Stream management

Recommendations

Minimizing Communication Overhead in Window-Based Parallel Complex Event Processing
DEBS '17: Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems

Distributed Complex Event Processing has emerged as a well-established paradigm to detect situations of interest from basic sensor streams, building an operator graph between sensors and applications. In order to detect event patterns that correspond to ...
An evaluation of speculative instruction execution on simultaneous multithreaded processors

Modern superscalar processors rely heavily on speculative execution for performance. For example, our measurements show that on a 6-issue superscalar, 93% of committed instructions for SPECINT95 are speculative. Without speculation, processor resources ...
Tuning Compiler Optimizations for Simultaneous Multithreading
Special issue on the 30th annual ACM/IEEE international symposium on microarchitecture, part II

Simultaneous Multithreading (SMT) is a processor architectural technique that promises to significantly improve the utilization and performance of modern wide-issue superscalar processors. An SM T processor is capable of issuing multiple instructions ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Middleware '17: Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference

December 2017

268 pages

ISBN:9781450347204

DOI:10.1145/3135974

General Chairs:
K. R. Jayaram
IBM T. J. Watson Research Center
,
Anshul Gandhi
Stony Brook University
,
Program Chairs:
Bettina Kemme
McGill University
,
Peter Pietzuch
Imperial College London

Copyright © 2017 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 the author(s) 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

ACM: Association for Computing Machinery

In-Cooperation

USENIX Assoc: USENIX Assoc
IFIP

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 December 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

DFG

Conference

Middleware '17

Sponsor:

ACM

Middleware '17: 18th International Middleware Conference

December 11 - 15, 2017

Nevada, Las Vegas

Acceptance Rates

Middleware '17 Paper Acceptance Rate 20 of 85 submissions, 24%;

Overall Acceptance Rate 203 of 948 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
256
Total Downloads

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

Reflects downloads up to 11 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
Gulisano VMargara A(2024)Aggregates are all you need (to bridge stream processing and Complex Event Recognition)Proceedings of the 18th ACM International Conference on Distributed and Event-based Systems10.1145/3629104.3666032(66-77)Online publication date: 24-Jun-2024
https://dl.acm.org/doi/10.1145/3629104.3666032
Boughzala BGärtner CKoldehofe BZhou YChrysanthis PGulisano V(2022)Window-based parallel operator execution with in-network computingProceedings of the 16th ACM International Conference on Distributed and Event-Based Systems10.1145/3524860.3539804(91-96)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1145/3524860.3539804
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
Sahal RAlsamhi SBreslin JAli M(2021)Industry 4.0 towards Forestry 4.0: Fire Detection Use CaseSensors10.3390/s2103069421:3(694)Online publication date: 20-Jan-2021
https://doi.org/10.3390/s21030694
Giatrakos NKougioumtzi EKontaxakis ADeligiannakis AKotidis YDemartini GZuccon GCulpepper JHuang ZTong H(2021)EasyFlinkCEPProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482094(3029-3033)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482094
Peros SAras EJoosen WHughes D(2020)Kairos: a self-configuring approach for short and accurate event timeouts in IoTMobiQuitous 2020 - 17th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services10.1145/3448891.3448917(347-356)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1145/3448891.3448917
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
Talebi MSharifi MKalantari M(2020)ACEP: an adaptive strategy for proactive and elastic processing of complex eventsThe Journal of Supercomputing10.1007/s11227-020-03454-0Online publication date: 26-Oct-2020
https://doi.org/10.1007/s11227-020-03454-0
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