Streaming -Algorithmus

Im Informatik, Streaming -Algorithmen sind Algorithmen für die Verarbeitung Datenströme in dem der Eingang als dargestellt wird Reihenfolge von Gegenständen und kann nur in wenigen Pässen untersucht werden (normalerweise nur einer). In den meisten Modellen haben diese Algorithmen Zugriff auf einen begrenzten Speicher (im Allgemeinen logarithmisch in der Größe und/oder dem Maximalwert im Strom). Sie können auch eine begrenzte Verarbeitungszeit pro Gegenstand haben.

Diese Einschränkungen können bedeuten, dass ein Algorithmus eine ungefähre Antwort auf der Grundlage einer Zusammenfassung oder "Skizze" des Datenstroms erzeugt.

Geschichte

Obwohl Streaming -Algorithmen bereits von Munro und Paterson untersucht worden waren^[1] bereits 1978 sowie Philippe Flajolet und G. Nigel Martin 1982/83,^[2] Das Gebiet der Streaming -Algorithmen wurde erstmals in einem Artikel von 1996 von 1996 formalisiert und populär gemacht Noga Alon, Yossi Matias, und Mario Szegedy.^[3] Für dieses Papier gewannen die Autoren später die Gödel -Preis 2005 "für ihren grundlegenden Beitrag zu Streaming -Algorithmen". Seitdem gab es eine große Arbeit, die sich um Datenstroming -Algorithmen konzentriert, die ein vielfältiges Spektrum von Informatikbereichen wie Theorie, Datenbanken, Netzwerk und Verarbeitung natürlicher Sprache umfassen.

Semi-Streaming-Algorithmen wurden 2005 als Entspannung von Streaming-Algorithmen für Graphen eingeführt.^[4] in dem der zulässige Raum in der Anzahl der Eckpunkte linear ist n, aber nur logarithmisch in der Anzahl der Kanten m. Diese Entspannung ist für dichte Graphen immer noch von Bedeutung und kann interessante Probleme (wie die Konnektivität) lösen, die unlöslich sind ${\ displayStyle o (n)}$ Platz.

Modelle

Datenstrommodell

Im Datenstrommodell werden einige oder alle Eingaben als endliche Abfolge von Ganzzahlen (aus einer endlichen Domäne) dargestellt, die im Allgemeinen nicht verfügbar ist Zufallszugriff, kommt aber stattdessen einzeln in einem "Stream" an.^[5] Wenn der Strom Länge hat n Und die Domäne hat die Größe mAlgorithmen sind im Allgemeinen eingeschränkt, um Platz zu verwenden, das ist logarithmisch in m und n. Sie können im Allgemeinen nur eine kleine ständige Anzahl von Pässen über den Strom machen, manchmal gerade gerecht eines.^[6]

Dreh- und Registrierungsmodelle

Ein Großteil der Streaming -Literatur befasst sich mit Computerstatistiken zu Frequenzverteilungen, die zu groß sind, um gespeichert zu werden. Für diese Klasse von Problemen gibt es einen Vektor ${\ displaystyle \ mathbf {a} = (a_ {1}, \ dots, a_ {n})}$ (initialisiert an den Nullvektor ${\ displaystyle \ mathbf {0}}$) Das hat Aktualisierungen in einem Stream vorgestellt. Das Ziel dieser Algorithmen ist es, Funktionen von zu berechnen ${\ displaystyle \ mathbf {a}}$ Nutzbar weniger Platz zu nutzen, als es brauchen würde, um darzustellen ${\ displaystyle \ mathbf {a}}$ genau. Es gibt zwei gemeinsame Modelle für die Aktualisierung solcher Streams, die als "Registrierkasse" und "Drehstil" -Modelle bezeichnet werden.^[7]

Im Speichermodell befindet sich jedes Update aus dem Formular ${\ displayStyle \ Langle I, C \ Rangle}$, so dass ${\ displayStyle a_ {i}}$ wird durch eine positive Ganzzahl erhöht ${\ displayStyle c}$. Ein bemerkenswerter Sonderfall ist wann ${\ displayStyle c = 1}$ (Es sind nur Einheiteneinfügungen gestattet).

Im Drehkreuzmodell befindet sich jedes Update aus dem Formular ${\ displayStyle \ Langle I, C \ Rangle}$, so dass ${\ displayStyle a_ {i}}$ wird durch eine (möglicherweise negative) Ganzzahl erhöht ${\ displayStyle c}$. Im Modell "Strict Drehs", nein${\ displayStyle a_ {i}}$ kann zu irgendeinem Zeitpunkt weniger als Null sein.

Schiebefenstermodell

Mehrere Papiere betrachten auch das Modell "Schiebfenster". In diesem Modell ist die Funktion des Interesses das Berechnen eines Fensters mit fester Größe im Stream. Im Verlauf des Streams werden Elemente vom Ende des Fensters aus der Prüfung entfernt, während neue Elemente aus dem Stream ihren Platz einnehmen.

Neben den oben genannten frequenzbasierten Problemen wurden auch einige andere Arten von Problemen untersucht. Viele Diagrammprobleme werden in der Einstellung gelöst, wo die Adjazenzmatrix oder der Adjazenzliste der Grafik wird in einer unbekannten Reihenfolge gestreamt. Es gibt auch einige Probleme, die sehr von der Reihenfolge des Stroms abhängen (d. H. Asymmetrische Funktionen), wie z.

Auswertung

Die Leistung eines Algorithmus, der auf Datenströmen arbeitet, wird an drei grundlegenden Faktoren gemessen:

• Die Anzahl der übergeht der Algorithmus muss über den Strom versehen.
• Der verfügbare Speicher.
• Die Laufzeit des Algorithmus.

Diese Algorithmen haben viele Ähnlichkeiten mit Online -Algorithmen Da beide Entscheidungen treffen müssen, bevor alle Daten verfügbar sind, aber nicht identisch sind. Datenstromalgorithmen haben nur einen begrenzten Speicher, aber sie können Maßnahmen möglicherweise aufschieben, bis eine Gruppe von Punkten ankommt, während Online -Algorithmen Maßnahmen ergreifen müssen, sobald jeder Punkt ankommt.

Wenn der Algorithmus ein Annäherungsalgorithmus ist, ist die Genauigkeit der Antwort ein weiterer Schlüsselfaktor. Die Genauigkeit wird oft als als angegeben ${\ displayStyle (\ epsilon, \ delta)}$ Annäherung, was bedeutet, dass der Algorithmus einen Fehler von weniger als erreicht ${\ displayStyle \ Epsilon}$ mit Wahrscheinlichkeit ${\ displayStyle 1- \ Delta}$.

Anwendungen

Streaming -Algorithmen haben mehrere Anwendungen in Networking wie Überwachungsnetzwerkverbindungen für ElefantenströmeZählen der Anzahl verschiedener Strömungen, Schätzung der Verteilung der Flussgrößen usw.^[8] Sie haben auch Anwendungen in Datenbanken, z. B. die Schätzung der Größe von a beitreten.

Einige Streaming -Probleme

Frequenzmomente

Das kTH Frequenzmoment einer Reihe von Frequenzen ${\ displaystyle \ mathbf {a}}$ ist definiert als ${\ displaystyle f_ {k} (\ mathbf {a}) = \ sum _ {i = 1}^{n} a_ {i}^{k}}$.

Der erste Moment ${\ displayStyle f_ {1}}$ ist einfach die Summe der Frequenzen (d. H. Die Gesamtzahl). Der zweite Moment ${\ displayStyle f_ {2}}$ ist nützlich für die Berechnung statistischer Eigenschaften der Daten, wie z. Gini-Koeffizient Variation. ${\ displayStyle f _ {\ infty}}$ ist definiert als die Frequenz der häufigsten Elemente.

Das Samenpapier von Alon, Matias und Szegedy befassten sich mit dem Problem der Schätzung der Frequenzmomente.

Berechnung der Frequenzmomente

Ein direkter Ansatz, um die Frequenzmomente zu finden, erfordert die Wartung eines Registers m_i Für alle unterschiedlichen Elemente a_i ∈ (1,2,3,4, ...,N) Dies erfordert mindestens Speicher der Ordnung ${\ displayStyle \ Omega (n)}$.^[3] Wir haben jedoch Platzeinschränkungen und benötigen einen Algorithmus, der in einem viel niedrigeren Speicher berechnet wird. Dies kann durch die Verwendung von Approximationen anstelle von genauen Werten erreicht werden. Ein Algorithmus, der eine berechnet (ε, δ) Annäherung von F_k, wo F'_k ist der (ε, δ)- angenäherter Wert von F_k.^[9] Wo ε ist der Annäherungsparameter und δ ist der Vertrauensparameter.^[10]

Berechnung F₀ (Unterschiedliche Elemente in einem Datastream)

FM-Sketch-Algorithmus

Flajolet et al. in ^[2] eingeführte probabilistische Zählmethode, die von einem Papier von inspiriert wurde Robert Morris.^[11] Morris in seiner Zeitung sagt, wenn das Erfordernis der Genauigkeit fallen gelassen wird, ein Zähler n kann durch einen Zähler ersetzt werden Protokoll n das kann in gespeichert werden Protokollprotokoll n Bits.^[12] Flajolet et al. in ^[2] verbesserte diese Methode mit einer Hash -Funktion h Es wird angenommen L).

${\ displayStyle H: [m] \ rightarrow [0,2^{l} -1]}$

Lassen bisschen(y, k) repräsentieren das KTH -Bit in der binären Darstellung von y

$oder$

Lassen ${\ displayStyle \ rho (y)}$ repräsentiert die Position des am wenigsten signifikanten 1-Bit in der binären Darstellung von y_i mit einer geeigneten Konvention für ${\ displayStyle \ rho (0)}$.

$oder L & {\ text {if}} y = 0 \ end {cases}}}$

Lassen A Seien Sie die Abfolge des Datenstroms der Länge M deren Kardinalität muss bestimmt werden. Lassen BITMAP [0 ...L - 1] der

Hash -Raum, wo der ρ(Hadervalues) sind aufgenommen. Der folgende Algorithmus bestimmt dann die ungefähre Kardinalität von A.

Prozedur fm-sketch: für i in 0 bis l-1 do bitmap [i]: = 0 ende für x in a: do index: = ρ (Hash (x)) Wenn bitmap [index] = 0 dann Bitmap [INDEX) ]: = 1 Ende, wenn Ende für b: = Position der linken meisten 0 Bit Bitmap [] zurücks 2 ^ B

Wenn es gibt N Unterschiedliche Elemente in einem Datenstrom.

• Zum ${\ displayStyle i \ gg \ log (n)}$ dann BITMAP[i] ist sicherlich 0
• Zum ${\ displayStyle i \ ll \ log (n)}$ dann BITMAP[i] ist sicher 1 1
• Zum ${\ displayStyle i \ apprx \ log (n)}$ dann BITMAP[i] ist ein Rand der 0er und eines 1er

K-Minimum -Wertalgorithmus

Der vorherige Algorithmus beschreibt den ersten Versuch, ungefähr zu approximieren F₀ im Datenstrom von Flajolet und Martin. Ihr Algorithmus wählt eine zufällige Hash -Funktion aus, die sie annehmen, die Hash -Werte im Hash -Raum einheitlich zu verteilen.

Bar-Yossef et al. in ^[10] eingeführter K-Minimum-Wert-Algorithmus zur Bestimmung der Anzahl verschiedener Elemente im Datenstrom. Sie verwendeten eine ähnliche Hash -Funktion h die auf [0,1] als normalisiert werden können ${\ displayStyle H: [m] \ rightarrow [0,1]}$. Aber sie haben ein Grenze festgelegt t zur Anzahl der Werte im Hash -Raum. Der Wert von t wird von der Bestellung angenommen ${\ displayStyle o \ links ({\ dfrac {1} {\ varepsilon _ {2}} \ rechts)}}$ (d. h. weniger Annäherungswerte ε erfordert mehr t). Der KMV -Algorithmus hält nur t-Smallest Hash -Werte im Hash -Raum. Immerhin m Werte des Streams sind angekommen, ${\ displayStyle \ upsilon = \ mathrm {max} (h (a_ {i}))}$ wird zur Berechnung verwendet${\ displayStyle f '_ {0} = {\ dfrac {t} {\ upsilon}}}$. Das heißt, in einem nahezu einheitlichen Hash-Raum erwarten sie mindestens Mist t Elemente weniger als sein ${\ displayStyle o \ links ({\ dfrac {t} {f_ {0}}} \ rechts)}$.

Verfahren 2 K-Minimum-Wert initialisieren Sie die ersten t-Werte von kmv für a in a1 bis ein do if h (a) <max (kmv), entfernen T/Max (KMV)

Komplexitätsanalyse von KMV

Der KMV -Algorithmus kann in implementiert werden $oder$ Speicherplatz Platz. Jeder Hash -Wert erfordert Platz der Ordnung ${\ displayStyle o (\ log (m))}$ Speicherbits. Es gibt Hash -Werte der Reihenfolge ${\ displayStyle o \ links ({\ dfrac {1} {\ varepsilon _ {2}} \ rechts)}}$. Die Zugangszeit kann reduziert werden, wenn wir die speichern t Hash -Werte in einem binären Baum. Somit wird die zeitliche Komplexität auf reduziert auf $oder$.

Berechnung F_k

Alon et al. Schätzungen F_k durch Definieren von zufälligen Variablen, die innerhalb von gegebenem Raum und Zeit berechnet werden können.^[3] Der erwartete Wert von Zufallsvariablen ergibt den ungefähren Wert von F_k.

Nehmen Sie die Länge der Sequenz an m ist im Voraus bekannt. Erstellen Sie dann eine zufällige Variable X folgendermaßen:

• Auswählen a_p ein zufälliges Mitglied der Sequenz sein A mit Index at p, ${\ displayStyle a_ {p} = l \ in (1,2,3, \ ldots, n)}$
• Lassen ${\ displayStyle r = | \ {q: q \ geq p, a_ {q} = l \} |}$, repräsentiert die Anzahl der Vorkommen von l Innerhalb der Mitglieder der Sequenz A folgen a_p.
• Zufällige Variable ${\ displayStyle x = m (r^{k}-(r-1)^{k})}$.

Davon ausgehen S₁ bestellen ${\ displayStyle o (n ^{1-1/k}/\ lambda ^{2})}$ und S₂ bestellen ${\ displayStyle o (\ log (1/\ varepsilon))}}$. Algorithmus nimmt S₂ zufällige Variable ${\ displayStyle y_ {1}, y_ {2}, ..., y_ {s2}}$ und gibt den Median aus ${\ displayStyle y}$ . Wo Y_i ist der Durchschnitt von X_ij wobei 1 ≤ j ≤ S₁.

Berechnen Sie nun die Erwartung einer zufälligen Variablen E(X).

$oder K}-(j-1)^{k}) \\ & = & {\ frac {m} {m}} [(1^{k}+(2^{k} -1^{k})+ \ ldots+(m_ {1}^{k}-(m_ {1} -1)^{k}) \\ && \;+\; (1^{k}+(2^{k} -1 ^{k})+\ ldots+(m_ {2}^{k}-(m_ {2} -1)^{k})+\ ldots \\ && \;+\; (1^{k} +(2^{k} -1^{k}) +\ ldots +(m_ {n}^{k}-(m_ {n} -1)^{k})] \\ & = & \ sum _ {i = 1}^{n} m_ {i}^{k} = f_ {k} \ end {Array}}}$

Komplexität von F_k

Vom Algorithmus zu berechnen F_k oben diskutiert werden wir sehen, dass jede zufällige Variable X speichert Wert von a_p und r. Also, um zu berechnen X Wir müssen nur aufrechterhalten Protokoll(n) Bits zum Aufbewahren a_p und Protokoll(n) Bits zum Aufbewahren r. Gesamtzahl der Zufallsvariablen X wird sein ${\ displayStyle s_ {1}*s_ {2}}$.

Daher ist die Gesamtraumkomplexität, die der Algorithmus nimmt ${\ displayStyle o \ links ({\ dfrac {k \ log {1 \ Over \ varepsilon}} {\ lambda ^{2}}} n ^{1- {1 \ Over K} \ links (\ log n+\ \ \ {1 \ log m \ rechts) \ rechts)}$

Einfacherer Ansatz zur Berechnung F₂

Der vorherige Algorithmus berechnet ${\ displayStyle f_ {2}}$ in der Reihenfolge der ${\ displayStyle o ({\ sqrt {n}} (\ log m+\ log n))}$ Speicherbits. Alon et al. in ^[3] vereinfacht diesen Algorithmus mithilfe einer vierzweigen unabhängigen Zufallsvariablen mit zugeordneten Werten ${\ displayStyle \ {-1,1 \}}$.

Dies reduziert die Berechnung der Komplexität weiter ${\ displayStyle f_ {2}}$ zu $oder$

Häufige Elemente

Im Datenstrommodell die häufiges Elementproblem ist, eine Reihe von Elementen auszugeben, die mehr als einen festen Anteil des Streams darstellen. Ein Sonderfall ist der Mehrheitsproblem, was bedeutet, ob ein Wert einen Großteil des Stroms darstellt oder nicht.

Führen Sie formell eine positive Konstante fest, c > 1, lass die Länge des Stroms sein m, und lass f_i bezeichnen die Wertfrequenz i im Strom. Das Problem der häufigen Elemente besteht darin, die auszugeben einstellen { i | f_i > m/c}.^[13]

Einige bemerkenswerte Algorithmen sind:

• Boyer -Moore -Mehrheitsstimmenalgorithmus
• Graf-min-Skizze
• Verlustbezählung
• Mehrstufig Blütefilter
• MISRA -GRIES -Zusammenfassung

Ereigniserkennung

Das Erkennen von Ereignissen in Datenströmen erfolgt häufig unter Verwendung eines schweren Hitter -Algorithmus wie oben aufgeführt: Die häufigsten Elemente und ihre Frequenz werden unter Verwendung eines dieser Algorithmen bestimmt, dann wird die größte Erhöhung gegenüber dem vorherigen Zeitpunkt als Trend angegeben. Dieser Ansatz kann durch Verwendung exponentiell gewichteter Verfeinerung verfeinert werden Gleitende Mittelwerte und Varianz für die Normalisierung.^[14]

Verschiedene Elemente zählen

Zählen Sie die Anzahl der unterschiedlichen Elemente in einem Strom (manchmal als das genanntF₀ Moment) ist ein weiteres Problem, das gut untersucht wurde. Der erste Algorithmus dafür wurde von Flajolet und Martin vorgeschlagen. In 2010, Daniel Kane, Jelani Nelson Und David Woodruff fand einen asymptotisch optimalen Algorithmus für dieses Problem.^[15] Es verwendet O(ε² + log d) Raum, mit O(1) Worst-Case-Update- und Berichtszeiten sowie universelle Hash-Funktionen und a r-Se unabhängige Hashfamilie wo r = Ω (log (1//ε) / Protokollprotokoll (1 / /ε)).

Entropie

Die (empirische) Entropie einer Reihe von Frequenzen ${\ displaystyle \ mathbf {a}}$ ist definiert als ${\ displayStyle f_ {k} (\ mathbf {a}) = \ sum _ {i = 1}^{n} {\ frac {a_ {i} {m}} \ log {\ frac {a_ {i}} {m}} \ {\ frac {a_ {i} }{m}}}$, wo ${\ displayStyle m = \ sum _ {i = 1}^{n} a_ {i}}$.

Online lernen

Lernen Sie ein Modell (z. B. a Klassifikator) durch einen einzigen Pass über ein Trainingssatz.

• Feature Hashing
• Stochastischer Gradientenabstieg

Untergrenzen

Für viele untersuchte Probleme mit dem Datenstreaming wurden untere Grenzen berechnet. Bei weitem die häufigste Technik für die Berechnung dieser unteren Grenzen verwendet Kommunikationskomplexität.

Siehe auch

• Datenstromabbau
• Data stream clustering
• Online -Algorithmus
• Stream -Verarbeitung
• Sequentieller Algorithmus

Anmerkungen

Verweise

• Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), "Die Raumkomplexität der Annäherung der Frequenzmomente", Journal of Computer and System Sciences, 58 (1): 137–147, doi:10.1006/jcs.1997.1545, ISSN 0022-0000. Zuerst veröffentlicht als Alon, Noga; Matias, Yossi; Szegedy, Mario (1996), "Die Raumkomplexität der Annäherung an die Frequenzmomente", Verfahren des 28. ACM -Symposiums über die Computertheorie (STOC 1996), S. 20–29, Citeseerx 10.1.1.131.4984, doi:10.1145/237814.237823, ISBN 978-0-89791-785-8, S2CID 1627911.
• Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002), "Modelle und Probleme in Datenstromsystemen", Verfahren des 21. ACM Sigmod-Sigact-Sigart-Symposiums über Prinzipien von Datenbanksystemen (Pods 2002) (PDF), S. 1–16, Citeseerx 10.1.1.138.190, doi:10.1145/543613.543615, ISBN 978-1581135077, S2CID 2071130.
• Gilbert, A. C.; Kotidis, Y.; Muthukrishnan, S.; Strauss, M. J. (2001), "Surfenwavelets in Streams: Ein-Pass-Zusammenfassungen für ungefähre Gesamtfragen" (PDF), Verfahren der Internationalen Konferenz über sehr große Datenbasis: 79–88.
• Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). "Ein optimaler Algorithmus für das Problem mit unterschiedlichen Elementen". Verfahren des neunundzwanzigsten ACM-Sigmod-Sigact-Sigart-Symposiums über Prinzipien von Datenbanksystemen. Pods '10. New York, NY, USA: ACM. S. 41–52. Citeseerx 10.1.1.164.142. doi:10.1145/1807085.1807094. ISBN 978-1-4503-0033-9. S2CID 10006932..
• Karp, R. M.; Papadimitriou, C. H.; Shenker, S. (2003), "Ein einfacher Algorithmus zum Auffinden häufiger Elemente in Bächen und Taschen", ACM -Transaktionen auf Datenbanksystemen, 28 (1): 51–55, Citeseerx 10.1.1.116.8530, doi:10.1145/762471.762473, S2CID 952840.
• Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, jun; Zhang, Hui (2006), "Datenstreaming -Algorithmen zur Schätzung der Entropie des Netzwerkverkehrs", Verfahren der gemeinsamen internationalen Konferenz über Messung und Modellierung von Computersystemen (ACM Sigmetrics 2006) (PDF), p. 145, doi:10.1145/1140277.1140295, HDL:1802/2537, ISBN 978-1595933195, S2CID 240982^{[Permanent Dead Link]}.
• Xu, Jun (Jim) (2007), Ein Tutorial zum Streaming von Netzwerkdaten (PDF).
• Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., "Lernen verschachtelte Konzepte mit begrenzter Lagerung", Proceeding Ijcai'91 Proceedings der 12. Internationalen gemeinsamen Konferenz über künstliche Intelligenz - Band - Band - Band - Volumen 2, Seiten 777-782, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA © 1991
• Morris, Robert (1978), "zählen eine große Anzahl von Ereignissen in kleinen Registern", Kommunikation der ACM, 21 (10): 840–842, doi:10.1145/359619.359627, S2CID 36226357.