Datenstrom-Algorithmen „teilen und erobern“

Welche nützlichen Algorithmen gibt es, die mit großen Datenströmen arbeiten und deren Ergebnisse relativ klein sind, und man kann das Ergebnis für eine Mischung aus zwei Datenströmen berechnen, indem man deren Ergebnisse irgendwie zusammenführt?

Ich kann einige nennen:

• Die offensichtlichen Dinge wie Summe, Min, Max, Zählung, Top-K usw.
• Ungefähre sogenannte "skizzenbasierte" Stream-Algorithmen für Histogramme, die unterschiedliche Elemente zählen oder Quantile berechnen

Welche anderen gibt es?

(Ich bin interessiert, weil ich ein Hobbyprojekt zur Überwachung verteilter Systeme schreibe, dessen Nützlichkeit direkt durch die Nützlichkeit solcher Algorithmen bestimmt wird.)

Guha et al. '03 geben einen Näherungsalgorithmus für das k-Median-Clustering im Streaming-Modell an. Ihr Algorithmus unterteilt die Daten in disjunkte Teile, ermittelt O (k) -Zentren für jedes disjunkte Teil und kombiniert dann die Ergebnisse, um die k-Zentren zu erhalten. Dies scheint die Art von Algorithmus zu sein, nach der Sie suchen.

$\varepsilon$$\varepsilon$$i^{\text{th}}$$(i-1)^{\text{th}}$-level stream und level 0 ist der ursprüngliche stream). Dies ist im Wesentlichen ein Bottom-up-Rendering einer Divide-and-Conquer-Strategie. mit Aktualisierungen entlang der "Kante" des Rekursionsbaums. In der Struktur ist es dem von Lev erwähnten Aufsatz von Guha et al. Sehr ähnlich.

Ich habe eine Arbeit gefunden ( "Verteilen von frequenzabhängigen Datenstromberechnungen" ), die besagt, dass jede Funktion der Frequenzverteilung des Stroms zusammengeführt werden kann (obwohl dies keine explizite und effiziente Konstruktion für die Zusammenführungsoperation darstellt). Und der Beweis scheint sehr interessant zu sein, da es sich um eine Ringtheorie handelt. Lesen Sie den vorherigen Artikel desselben Autors ( "Untere Schranken für die Frequenzschätzung von Datenströmen" ), dessen Hauptergebnis als Grundlage für diesen verwendet wird.

Das erinnert mich an den dritten Homomorphismus-Satz ...

Die Forschung zu Abfragesprachen für kontinuierliche Streams kann einige Erkenntnisse liefern. Eine solche Sprache ist CQL , von dem ich glaube, dass es von Oracle übernommen wird. Die Sprachen ermöglichen die Berechnung von Funktionen über Schiebefenster des Streams (einschließlich Fenster der Größe 1). Diese Bachelorarbeit gibt einen aktuellen Überblick über die Sprache mit einigen Beispielen. Dieses Papier gibt einen Überblick über einige Stream-Verarbeitungssprachen, die nützlich sein sollten, um Links zu anderen verwandten Forschungsergebnissen zu finden.

Ich weiß, dass dies Ihre Frage nicht direkt beantwortet, aber es sollte Sie mit Recherchen in Verbindung bringen, die von Personen durchgeführt wurden, die von demselben Ausgangspunkt abweichen.

Diese Frage scheint mir ein bisschen kreisförmig. Wenn das Problem die gewünschte Eigenschaft hat, gibt es einen auf Skizzen und Zusammenführungen basierenden Algorithmus. Wie oben erwähnt, gibt es Arbeiten zu Clustering, Approximationen und Coresets, die dies ermöglichen. Außerdem ermöglichen die meisten Streaming-Algorithmen das Zusammenführen von Streams, indem nur (konzeptionell) ein Stream mit dem anderen verkettet wird.

Ich bin mir auch nicht sicher, ob Top-K-Streaming-Algorithmen zusammengeführt werden können - aber ich könnte mich irren.

Es tut mir leid, dass Sie sich damit nicht auskennen, aber ich dachte, Sie sollten sich einige Arbeiten zur verteilten kontinuierlichen Überwachung von Streams ansehen, bei denen Sie mehrere Streams erhalten. Ziel ist es, eine aggregierte Statistik an einer zentralen Überwachungsstelle zu überwachen und gleichzeitig die Kommunikation zu minimieren. Das Modell klingt für mich eng mit Ihrer Motivation verbunden. Schauen Sie sich die Referenzen in Muthus Buch an . Ein Papier ist dies .

Gangulys Artikel ist auch sehr interessant.