Parallel complex event processing to meet probabilistic latency bounds II

• Applicants: Professorin Dr. Sukanya Bhowmik; Professor Dr. Kurt Rothermel
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2015 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 268797282

• Final Report Year: 2023

Final Report Abstract

Complex event processing (CEP) uses continuous queries to detect patterns of interest in streams of primitive events. The detection of patterns in time is paramount in many application fields, such as online stock trading, surveillance, traffic monitoring. There is a lot of work on investigating low-latency CEP under the assumption that there are unlimited resources available. Most of these works solve the problem by increasing the degree of parallelism, i.e., allocating additional resources for operator processing. However, there are also situations where the monetary budget for running a CEP system and/or the available resources are limited, e.g., a CEP implementation on IoT edge nodes due to privacy or latency reasons. In a system with limited resources, one way to reduce the incoming load of the operator is to perform load shedding. The obvious disadvantage of load shedding is the degradation of the quality of result (QoR). As a result, the overall goal of Precept II was to develop load shedding methods that ensure a given latency bound for a CEP application, while maximizing the QoR perceived by the application. While there is a significant amount of work on load shedding in stream processing systems, to the best of our knowledge, we are among the first to perform a detailed investigation of this problem in the CEP domain. In this project, we propose five load shedding approaches that decrease the load of a single CEP operator in case of overload, thus enabling the operator to maintain a given latency bound. Our proposed load shedding approaches are light-weight and cover a wide range of load shedding classes in the CEP domain. In particular, we propose two black-box approaches to drop events from incoming event streams and two white-box approaches to drop events and internal state of the operator. Additionally, we propose an approach for real-time video analytics operators. Finally, we propose a load shedding technique for a multi-operator CEP application, where we show the advantages of having a global perspective to further improve upon the QoR of our local shedding approaches.

Publications

• A Comprehensive Survey on Parallelization and Elasticity in Stream Processing. ACM Computing Surveys, 52(2), 1-37.
  Röger, Henriette & Mayer, Ruben
  
• Combining it all: Cost minimal and low-latency stream processing across distributed heterogeneous infrastructures. In Proc. of the 20th International Middleware Conference. ACM, 2019
  Henriette Röger; Sukanya Bhowmik & Kurt Rothermel
  
• eSPICE. Proceedings of the 20th International Middleware Conference.
  Slo, Ahmad; Bhowmik, Sukanya & Rothermel, Kurt
  
• pSPICE: Partial Match Shedding for Complex Event Processing. 2019 IEEE International Conference on Big Data (Big Data).
  Slo, Ahmad; Bhowmik, Sukanya; Flaig, Albert & Rothermel, Kurt
  
• hSPICE. Proceedings of the 14th ACM International Conference on Distributed and Event-based Systems, 109-120.
  Slo, Ahmad; Bhowmik, Sukanya & Rothermel, Kurt
  
• A Framework for Decentralized Parallel Complex Event Processing on Heterogeneous Infrastructures. 2021 IEEE International Conference on Big Data (Big Data), 190-196.
  Roger, Henriette; Bhowmik, Sukanya & Linn, Tobias
  
• Load shedding in window-based complex event processing. PhD thesis, University of Stuttgart, Germany, 2022
  Ahmad Slo
  
• State-Aware Load Shedding From Input Event Streams in Complex Event Processing. IEEE Transactions on Big Data, 8(5), 1340-1357.
  Slo, Ahmad; Bhowmik, Sukanya & Rothermel, Kurt
  
• Grand perspective: Load shedding in distributed cep applications. CoRR, abs/2309.17183, 2023
  Henriette Röger; Sukanya Bhowmik & Kurt Rothermel
  
• gSPICE: Model-Based Event Shedding in Complex Event Processing. 2023 IEEE International Conference on Big Data (BigData), 263-270.
  Slo, Ahmad; Bhowmik, Sukanya & Rothermel, Kurt
  
• Utility-aware load shedding for real-time video analytics at the edge. CoRR, abs/2307.02409, 2023
  Enrique Saurez; Harshit Gupta; Henriette Röger; Sukanya Bhowmik; Umakishore Ramachandran & Kurt Rothermel