pSPICE: Partial Match Shedding for Complex Event Processing
Authors:
- 1 December 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 372-382
Abstract
Complex event processing (CEP) systems continuously process input event streams to detect patterns. Over time, the input event rate might fluctuate and overshoot the system’s capabilities. One way to reduce the overload on the system is to use load shedding. In this paper, we propose a load shedding strategy for CEP systems which drops a portion of the CEP operator’s internal state (a.k.a. partial matches) to maintain a given latency bound. The crucial question here is how many and which partial matches to drop so that a given latency bound is maintained while minimizing the degradation in the quality of results. In the stream processing domain, different load shedding strategies have been proposed that mainly depend on the importance of individual tuples. However, as CEP systems perform pattern detection, the importance of events is also influenced by other events in the stream. Our load shedding strategy uses Markov chain and Markov reward process to predict the utility/importance of partial matches to determine the ones to be dropped. In addition, we represent the utility in a way that minimizes the overhead of load shedding. Furthermore, we provide algorithms to decide when to start dropping partial matches and how many partial matches to drop. By extensively evaluating our approach on three real-world datasets and several representative queries, we show that the adverse impact of our load shedding strategy on the quality of results is considerably less than the impact of state-of-the-art load shedding strategies.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Scalable Pattern Sharing on Event Streams*2016
- THEMIS2016
- Load-aware shedding in stream processing systems2016
- Elastic complex event processing exploiting prediction2015
- Auto-approximation of graph computingProceedings of the VLDB Endowment, 2014
- Integrating scale out and fault tolerance in stream processing using operator state management2013
- Complex event detection at wire speed with FPGAsProceedings of the VLDB Endowment, 2010
- A stratified approach to progressive approximate joins2008
- High-performance complex event processing over streams2006
- Adaptive filters for continuous queries over distributed data streams2003