Zur Kurzanzeige

2022-05-20Dissertation DOI: 10.18452/24311
State Management for Efficient Event Pattern Detection
dc.contributor.authorZhao, Bo
dc.date.accessioned2022-05-20T08:08:01Z
dc.date.available2022-05-20T08:08:01Z
dc.date.issued2022-05-20none
dc.identifier.urihttp://edoc.hu-berlin.de/18452/25352
dc.description.abstractEvent Stream Processing (ESP) Systeme überwachen kontinuierliche Datenströme, um benutzerdefinierte Queries auszuwerten. Die Herausforderung besteht darin, dass die Queryverarbeitung zustandsbehaftet ist und die Anzahl von Teilübereinstimmungen mit der Größe der verarbeiteten Events exponentiell anwächst. Die Dynamik von Streams und die Notwendigkeit, entfernte Daten zu integrieren, erschweren die Zustandsverwaltung. Erstens liefern heterogene Eventquellen Streams mit unvorhersehbaren Eingaberaten und Queryselektivitäten. Während Spitzenzeiten ist eine erschöpfende Verarbeitung unmöglich, und die Systeme müssen auf eine Best-Effort-Verarbeitung zurückgreifen. Zweitens erfordern Queries möglicherweise externe Daten, um ein bestimmtes Event für eine Query auszuwählen. Solche Abhängigkeiten sind problematisch: Das Abrufen der Daten unterbricht die Stream-Verarbeitung. Ohne eine Eventauswahl auf Grundlage externer Daten wird das Wachstum von Teilübereinstimmungen verstärkt. In dieser Dissertation stelle ich Strategien für optimiertes Zustandsmanagement von ESP Systemen vor. Zuerst ermögliche ich eine Best-Effort-Verarbeitung mittels Load Shedding. Dabei werden sowohl Eingabeeevents als auch Teilübereinstimmungen systematisch verworfen, um eine Latenzschwelle mit minimalem Qualitätsverlust zu garantieren. Zweitens integriere ich externe Daten, indem ich das Abrufen dieser von der Verwendung in der Queryverarbeitung entkoppele. Mit einem effizienten Caching-Mechanismus vermeide ich Unterbrechungen durch Übertragungslatenzen. Dazu werden externe Daten basierend auf ihrer erwarteten Verwendung vorab abgerufen und mittels Lazy Evaluation bei der Eventauswahl berücksichtigt. Dabei wird ein Kostenmodell verwendet, um zu bestimmen, wann welche externen Daten abgerufen und wie lange sie im Cache aufbewahrt werden sollen. Ich habe die Effektivität und Effizienz der vorgeschlagenen Strategien anhand von synthetischen und realen Daten ausgewertet und unter Beweis gestellt.ger
dc.description.abstractEvent stream processing systems continuously evaluate queries over event streams to detect user-specified patterns with low latency. However, the challenge is that query processing is stateful and it maintains partial matches that grow exponentially in the size of processed events. State management is complicated by the dynamicity of streams and the need to integrate remote data. First, heterogeneous event sources yield dynamic streams with unpredictable input rates, data distributions, and query selectivities. During peak times, exhaustive processing is unreasonable, and systems shall resort to best-effort processing. Second, queries may require remote data to select a specific event for a pattern. Such dependencies are problematic: Fetching the remote data interrupts the stream processing. Yet, without event selection based on remote data, the growth of partial matches is amplified. In this dissertation, I present strategies for optimised state management in event pattern detection. First, I enable best-effort processing with load shedding that discards both input events and partial matches. I carefully select the shedding elements to satisfy a latency bound while striving for a minimal loss in result quality. Second, to efficiently integrate remote data, I decouple the fetching of remote data from its use in query evaluation by a caching mechanism. To this end, I hide the transmission latency by prefetching remote data based on anticipated use and by lazy evaluation that postpones the event selection based on remote data to avoid interruptions. A cost model is used to determine when to fetch which remote data items and how long to keep them in the cache. I evaluated the above techniques with queries over synthetic and real-world data. I show that the load shedding technique significantly improves the recall of pattern detection over baseline approaches, while the technique for remote data integration significantly reduces the pattern detection latency.eng
dc.language.isoengnone
dc.publisherHumboldt-Universität zu Berlin
dc.rights(CC BY 4.0) Attribution 4.0 Internationalger
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectDatenstromverarbeitungger
dc.subjectComplex event processingger
dc.subjectMustererkennungger
dc.subjectDatenbankmanagementsystemger
dc.subjectData stream processingeng
dc.subjectComplex event processingeng
dc.subjectPattern detectioneng
dc.subjectDatabase management systemseng
dc.subject.ddc004 Informatiknone
dc.titleState Management for Efficient Event Pattern Detectionnone
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-110-18452/25352-5
dc.identifier.doihttp://dx.doi.org/10.18452/24311
dc.date.accepted2022-03-01
dc.contributor.refereeWeidlich, Matthias
dc.contributor.refereeRothermel, Kurt
dc.contributor.refereeKoldehofe, Boris
dc.subject.rvkST 265
local.edoc.pages162none
local.edoc.type-nameDissertation
bua.departmentMathematisch-Naturwissenschaftliche Fakultätnone

Zur Kurzanzeige