Master Thesis MSTR-2021-54

BibliographyGroßkopf, Timo: Load shedding in complex event processing with probabilistic features.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 54 (2021).
60 pages, english.

Complex Event Processing (CEP) is a stream processing paradigm primarily searching for event type patterns in continuous event streams. Furthermore, load shedding is a common practice in CEP applications when resources are limited and under heavy load. Operators, which become a bottleneck due to bursts in event streams and therefore message queuing, drop event messages with a low matching probability to comply with their latency bound. Existing CEP load shedding mechanisms show a need for improvement if application queries consider an arithmetic relation between event attribute values, which are then called dependent attributes. In this case, incoming events of the same type must be differentiable in their individual matching probability, which bases on their dependent attribute values. This work introduces the Probabilistic Feature Shedding (PFS) approach, which leverages probability distributions of the dependent attribute values to derive thresholds as shed margins for incoming events. These thresholds categorize incoming events into probable and improbable events to fulfill the arithmetic relation. Improbable events are dispensable for their lower matching probability. The intention behind the PFS mechanism is, that existing shedding mechanisms are complemented with its functionality. In the course of this work, a random shedding mechanism and a distributed shedding approach with linear program solver are each extended with an implementation of the introduced PFS paradigm. Hence, extensive experiments on synthetic datasets as well as a real world dataset are executed with the different shedding paradigms and extensions. The results of all experiments confirm the expectation of a significant improvement in output quality, measured in the number of complex events. Furthermore, simulations show a linear dependency between probabilistic feature evaluation and processing time.

Full text and
other links
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Röger, Henriette; Bhowmik, Dr. Sukanya
Entry dateDecember 22, 2021
   Publ. Computer Science