Hintergrund

Odysseus ist ein an der Universität Oldenburg entwickeltes Datenstrommanagementsystem. Es ermöglicht die kontinuierliche Verarbeitung potenziell unendlicher Datenströme mithilfe deklarativ formulierter Anfragen. Weitere Informationen zum System sind unter https://odysseus.uni-oldenburg.de verfügbar.

Die Eigenschaften eines Datenstroms können sich während seiner Verarbeitung verändern. Beispiele sind eine dauerhafte Verschiebung von Messwerten, eine steigende Varianz, eine veränderte Werteverteilung oder ein Wechsel zwischen unterschiedlichen Betriebszuständen. Solche Veränderungen werden als Change oder Data Drift bezeichnet.

Anders als bei einer nachträglichen Analyse gespeicherter Daten müssen Veränderungen in einem Datenstrom möglichst zeitnah, mit begrenztem Speicherbedarf und ohne Kenntnis zukünftiger Ereignisse erkannt werden. Dafür existieren unterschiedliche inkrementelle Verfahren wie ADWIN, Page-Hinkley oder KSWIN. Bislang stehen solche Verfahren in Odysseus jedoch nicht als einheitlich verwendbare Anfrageoperatoren zur Verfügung.

Ziel der Arbeit

Ziel der Bachelorarbeit ist die Konzeption und prototypische Implementierung einer erweiterbaren Change-Detection-Komponente für Odysseus.

Benutzerinnen und Benutzer sollen innerhalb einer kontinuierlichen Anfrage festlegen können, welches Attribut eines Datenstroms durch welches Verfahren überwacht werden soll. Bei einer erkannten Veränderung soll der Operator ein entsprechendes Ereignis erzeugen oder die eingehenden Ereignisse mit zusätzlichen Metadaten versehen.

Eine beispielhafte Verwendung könnte folgendermaßen aussehen:

CHANGEDETECTION({

    attribute = 'temperature',

    method = 'ADWIN',

    key = 'sensorId',

    sensitivity = 0.002

})

Die genaue Syntax und Integration in die Anfragesprache sind im Rahmen der Arbeit zu entwickeln.

Die zentrale Forschungsfrage lautet:

Wie können unterschiedliche Change-Detection-Verfahren als einheitliche, zustandsbehaftete und effizient ausführbare Operatoren in ein Datenstrommanagementsystem integriert werden?

Aufgabenstellung

Im Rahmen der Arbeit sollen insbesondere folgende Aufgaben bearbeitet werden:

• Analyse etablierter Change-Detection-Verfahren für Datenströme

• Untersuchung geeigneter Integrationspunkte in Odysseus

• Entwurf einer einheitlichen Schnittstelle für unterschiedliche Detektoren

• Definition eines geeigneten Ausgabeformats für Warnungen und erkannte Veränderungen

• prototypische Implementierung ausgewählter Verfahren

• Integration der Verfahren in die Anfragesprache von Odysseus

• Unterstützung unabhängiger Detektorzustände für unterschiedliche Schlüssel

• Konzeption der Speicherung und Wiederherstellung des Detektorzustands

• Entwicklung synthetischer Testdaten mit kontrollierten Veränderungen

• experimentelle Evaluation der implementierten Verfahren

Mögliche Verfahren

Im Rahmen der Arbeit sollen mindestens zwei unterschiedliche Change-Detection-Verfahren betrachtet werden. Mögliche Kandidaten sind:

• ADWIN,

• Page-Hinkley,

• KSWIN,

• CUSUM,

• EWMA-basierte Verfahren.

Eine geeignete Auswahl wäre beispielsweise ADWIN und Page-Hinkley. Optional könnte KSWIN als drittes Verfahren ergänzt werden, um neben Mittelwertänderungen auch allgemeinere Veränderungen der Werteverteilung zu betrachten.

Die Arbeit soll keine vollständige Neuentwicklung der mathematischen Verfahren voraussetzen. Vorhandene Referenzimplementierungen dürfen untersucht werden. Die Integration in das zustandsbehaftete Verarbeitungsmodell von Odysseus und die vergleichende Evaluation bilden jedoch wesentliche Bestandteile der Arbeit.

Verhalten des Operators

Der entwickelte Operator soll konfigurierbar festlegen können:

• welches Attribut überwacht wird,

• welches Change-Detection-Verfahren eingesetzt wird,

• mit welchen Parametern der Detektor arbeitet,

• ob die Erkennung global oder getrennt nach einem Schlüssel erfolgt,

• ob ein Warnzustand und ein bestätigter Drift unterschieden werden,

• welche Daten beim Erkennen einer Veränderung ausgegeben werden.

Ein erzeugtes Änderungsergebnis könnte beispielsweise folgende Informationen enthalten:

sensorId

attribute

detectionTime

method

oldEstimate

newEstimate

confidence

detectorState

Dabei soll untersucht werden, welche Informationen verfahrensunabhängig bereitgestellt werden können.

Zustandsverwaltung

Change-Detection-Verfahren besitzen einen internen Zustand, beispielsweise ein adaptives Fenster, fortlaufende Statistiken oder gespeicherte Stichproben. Dieser Zustand muss für jeden überwachten Datenstrom und gegebenenfalls für jeden Schlüssel getrennt verwaltet werden.

Daraus ergeben sich unter anderem folgende Herausforderungen:

• potenziell große Anzahl unterschiedlicher Schlüssel,

• begrenzter Hauptspeicher,

• Bereinigung nicht mehr benötigter Zustände,

• thread-sichere Verarbeitung,

• Speicherung und Wiederherstellung im Fehlerfall,

• konsistentes Verhalten nach einem Recovery.

Das Zusammenspiel mit dem vorhandenen State-Management von Odysseus soll deshalb konzeptionell betrachtet und für mindestens einen Detektor prototypisch umgesetzt werden.

Fragestellungen

Die Arbeit soll unter anderem folgende Fragen untersuchen:

• Wie können unterschiedliche Detektoren über eine gemeinsame Schnittstelle angesprochen werden?

• Welche Parameter müssen innerhalb einer Odysseus-Anfrage konfigurierbar sein?

• Wie können unabhängige Detektorzustände pro Schlüssel effizient verwaltet werden?

• Wie beeinflusst die Ereignisrate die Erkennungsqualität und den Ressourcenverbrauch?

• Wie unterscheiden sich die Verfahren bei plötzlichen und schrittweisen Veränderungen?

• Wie empfindlich reagieren die Verfahren auf Ausreißer und Rauschen?

• Wie lassen sich Warnungen, bestätigte Veränderungen und Normalzustände einheitlich repräsentieren?

• Wie kann der Zustand eines Detektors gespeichert und nach einem Fehler wiederhergestellt werden?

Evaluation

Die implementierten Verfahren sollen anhand kontrollierter Datenströme evaluiert werden. Dabei sollen unterschiedliche Szenarien betrachtet werden:

• keine Veränderung,

• plötzliche Veränderung,

• graduelle Veränderung,

• kontinuierliche Verschiebung,

• vorübergehende Veränderung,

• einzelne Ausreißer,

• wiederkehrende Verteilungen.

Als Bewertungskriterien können verwendet werden:

• Erkennungsverzögerung,

• Anzahl falsch-positiver Meldungen,

• Anzahl nicht erkannter Veränderungen,

• Durchsatz,

• Verarbeitungslatenz,

• Speicherbedarf,

• Einfluss der Konfigurationsparameter,

• Aufwand zur Wiederherstellung des Detektorzustands.

Abgrenzung

Im Mittelpunkt steht die Erkennung von Veränderungen in ein- beziehungsweise niedrigdimensionalen Datenströmen.

Nicht zwingend Bestandteil der Arbeit sind:

• die Entwicklung eines neuen mathematischen Change-Detection-Verfahrens,

• die automatische Anpassung nachgelagerter Anfragen,

• die Verarbeitung hochdimensionaler Merkmalsräume,

• das Training und die automatische Aktualisierung von ML-Modellen,

• eine verteilte Zusammenführung von Driftmeldungen,

• die Implementierung sämtlicher existierender Detektoren.

Erwartete Ergebnisse

Am Ende der Arbeit sollen vorliegen:

• eine Analyse geeigneter Change-Detection-Verfahren,

• ein einheitliches Architektur- und Schnittstellenkonzept,

• mindestens zwei in Odysseus integrierte Detektoren,

• eine Einbindung in die Anfragesprache,

• eine Unterstützung schlüsselbasierter Detektorzustände,

• synthetische Testdaten mit kontrollierten Veränderungen,

• automatisierte Funktions- und Recoverytests,

• eine vergleichende Evaluation,

• eine Dokumentation der Verwendung und Erweiterungsmöglichkeiten.

Voraussetzungen

Hilfreich sind Kenntnisse oder Interesse in folgenden Bereichen:

• Programmierung mit Java,

• statistische Grundlagen,

• Datenstrukturen und Algorithmen,

• Datenstromverarbeitung,

• experimentelle Evaluation und Softwaretests.

Kenntnisse über Odysseus und Change-Detection-Verfahren werden nicht vorausgesetzt und können im Rahmen der Arbeit erworben werden.