Streaming-Algorithmus

In der Informatik verarbeiten Streaming - Algorithmen Eingabedatenströme als Sequenz von Elementen und durchlaufen die Daten typischerweise nur einmal (oder wenige Male). Diese Algorithmen sind für den Betrieb mit begrenztem Speicherplatz ausgelegt, der im Allgemeinen logarithmisch zur Größe des Datenstroms und/oder zum Maximalwert im Datenstrom ansteigt. Zudem kann die Verarbeitungszeit pro Element begrenzt sein.

Aufgrund dieser Einschränkungen liefern Streaming-Algorithmen oft nur Näherungswerte, die auf einer Zusammenfassung oder einem "Skizzen" des Datenstroms basieren.

Obwohl Streaming-Algorithmen bereits 1978 von Munro und Paterson ^{[ 1 ]} sowie 1982/83 von Philippe Flajolet und G. Nigel Martin ^{[ 2 ]} untersucht wurden , wurde das Gebiet der Streaming-Algorithmen erstmals 1996 in einer Arbeit von Noga Alon , Yossi Matias und Mario Szegedy formalisiert und popularisiert ^{[ 3 ]} . Für diese Arbeit erhielten die Autoren 2005 den Gödel-Preis „für ihren grundlegenden Beitrag zu Streaming-Algorithmen“. Seitdem ist eine Vielzahl von Arbeiten zu Datenstreaming-Algorithmen entstanden, die ein breites Spektrum an Informatikbereichen wie Theorie, Datenbanken, Netzwerke und Verarbeitung natürlicher Sprache abdecken .

Semi-Streaming-Algorithmen wurden 2005 als eine Vereinfachung der Streaming-Algorithmen für Graphen eingeführt ^{[ 4 ]} . Dabei ist der benötigte Speicherplatz linear in der Anzahl der Knoten n , aber nur logarithmisch in der Anzahl der Kanten m . Diese Vereinfachung ist auch für dichte Graphen sinnvoll und kann interessante Probleme (wie z. B. Konnektivität) lösen, die rein speichertechnisch nicht lösbar sind. ${\displaystyle o(n)}$

Im Datenstrommodell wird ein Teil oder die gesamte Eingabe als endliche Folge von ganzen Zahlen (aus einem endlichen Definitionsbereich) dargestellt, auf die im Allgemeinen nicht wahlfrei zugegriffen werden kann , sondern die nacheinander in einem „Datenstrom“ eintreffen. ^{[ 5 ]} Hat der Datenstrom die Länge n und der Definitionsbereich die Größe m , so ist der Speicherplatzbedarf von Algorithmen im Allgemeinen auf einen logarithmischen Wert in m und n beschränkt . Sie können im Allgemeinen nur eine kleine, konstante Anzahl von Durchläufen über den Datenstrom durchführen, manchmal nur einen . ^{[ 6 ]}

Ein Großteil der Literatur zum Thema Streaming befasst sich mit der Berechnung von Statistiken über Häufigkeitsverteilungen, die zu groß sind, um gespeichert zu werden. Bei dieser Problemklasse gibt es einen Vektor (initialisiert mit dem Nullvektor ), dem Aktualisierungen in einem Datenstrom zugeführt werden. Ziel dieser Algorithmen ist es, Funktionen zu berechnen, die deutlich weniger Speicherplatz benötigen, als für eine präzise Darstellung erforderlich wäre. Es gibt zwei gängige Modelle zur Aktualisierung solcher Datenströme: das „Kassemodell“ und das „Drehkreuzmodell“. ^{[ 7 ]}${\displaystyle \mathbf {a} =(a_{1},\dots ,a_{n})}$${\displaystyle \mathbf {0} }$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {a} }$

Im Kassenmodell hat jede Aktualisierung die Form , sodass um eine positive ganze Zahl erhöht wird . Ein bemerkenswerter Sonderfall ist der Fall, wenn (nur Einfügungen von Einheiten sind zulässig). ${\displaystyle \langle i,c\rangle }$${\displaystyle a_{i}}$${\displaystyle c}$${\displaystyle c=1}$

Im Turnstile-Modell hat jede Aktualisierung die Form , sodass um eine (möglicherweise negative) ganze Zahl erhöht wird . Im „strengen Turnstile“-Modell darf zu keinem Zeitpunkt ein kleiner als Null sein. ${\displaystyle \langle i,c\rangle }$${\displaystyle a_{i}}$${\displaystyle c}$${\displaystyle a_{i}}$

Mehrere Arbeiten befassen sich auch mit dem „Gleitfenster“-Modell. In diesem Modell wird die zu berechnende Funktion über ein Fenster fester Größe im Datenstrom berechnet. Während der Datenstrom fortschreitet, werden Elemente vom Ende des Fensters nicht mehr berücksichtigt, während neue Elemente aus dem Datenstrom an deren Stelle treten.

Neben den oben genannten frequenzbasierten Problemen wurden auch andere Problemtypen untersucht. Viele Graphprobleme werden in einem Szenario gelöst, in dem die Adjazenzmatrix oder die Adjazenzliste des Graphen in unbekannter Reihenfolge vorliegt. Es gibt auch Probleme, die stark von der Reihenfolge des Datenstroms abhängen (z. B. asymmetrische Funktionen), wie etwa das Zählen der Inversionen in einem Datenstrom oder das Finden der längsten aufsteigenden Teilfolge.

Die Leistungsfähigkeit eines Algorithmus, der auf Datenströmen arbeitet, wird anhand von drei grundlegenden Faktoren gemessen:

• Die Anzahl der Durchläufe, die der Algorithmus über den Datenstrom durchführen muss.
• Der verfügbare Speicher.
• Die Laufzeit des Algorithmus.

Diese Algorithmen weisen viele Ähnlichkeiten mit Online-Algorithmen auf , da beide Entscheidungen erfordern, bevor alle Daten verfügbar sind. Sie sind jedoch nicht identisch. Datenstromalgorithmen verfügen nur über begrenzten Speicher, können aber Aktionen bis zum Eintreffen einer Gruppe von Datenpunkten hinauszögern, während Online-Algorithmen sofort nach dem Eintreffen jedes einzelnen Datenpunkts handeln müssen.

Handelt es sich bei dem Algorithmus um einen Approximationsalgorithmus, so ist die Genauigkeit des Ergebnisses ein weiterer entscheidender Faktor. Die Genauigkeit wird oft als Näherungswert angegeben, was bedeutet, dass der Algorithmus mit einer Wahrscheinlichkeit von weniger als einen Fehler von erreicht . ${\displaystyle (\epsilon,\delta)}$${\displaystyle \epsilon }$${\displaystyle 1-\delta }$

Streaming-Algorithmen finden in der Netzwerktechnik vielfältige Anwendung, beispielsweise bei der Überwachung von Netzwerkverbindungen auf Elephant Flows , der Zählung unterschiedlicher Datenflüsse, der Schätzung der Verteilung von Datenflussgrößen usw. ^{[ 8 ]} Sie werden auch in Datenbanken eingesetzt, etwa zur Schätzung der Größe eines Joins .

Das k -te Frequenzmoment einer Menge von Frequenzen ist definiert als . ${\displaystyle \mathbf {a} }$${\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}}$

Das erste Moment ist einfach die Summe der Häufigkeiten (d. h. die Gesamtzahl). Das zweite Moment ist nützlich zur Berechnung statistischer Eigenschaften der Daten, wie beispielsweise des Gini-Koeffizienten . Es ist definiert als die Häufigkeit der häufigsten Elemente. ${\displaystyle F_{1}}$${\displaystyle F_{2}}$${\displaystyle F_{\infty }}$

Die bahnbrechende Arbeit von Alon, Matias und Szegedy befasste sich mit dem Problem der Schätzung der Frequenzmomente.

Ein direkter Ansatz zur Bestimmung der Frequenzmomente erfordert die Führung eines Registers m _{_i} für alle verschiedenen Elemente a _{_i} ∈ (1,2,3,4,..., N ) , was einen Speicherplatzbedarf von mindestens O(n²) erfordert . ^{[ 3 ]} Aufgrund von Speicherbeschränkungen benötigen wir jedoch einen Algorithmus mit deutlich geringerem Speicherbedarf. Dies lässt sich durch die Verwendung von Näherungen anstelle exakter Werte erreichen. Ein solcher Algorithmus berechnet eine ( ε,δ )-Approximation von F _{_k} , wobei F' _{_k} der ( ε,δ )-approximierte Wert von F_{_k} ist . ^{[ 9 ]} Hierbei ist ε der Approximationsparameter und δ der Konfidenzparameter. ^{[ 10 ]}${\displaystyle \Omega (N)}$

Flajolet et al. führten in ^{[ 2 ]} eine probabilistische Zählmethode ein, die von einer Arbeit von Robert Morris inspiriert wurde . ^{[ 11 ]} Morris argumentiert in seiner Arbeit, dass, wenn auf Genauigkeit verzichtet wird, ein Zähler n durch einen Zähler log n ersetzt werden kann , der in log log n Bits gespeichert werden kann. ^{[ 12 ]} Flajolet et al. verbesserten diese Methode in ^{[ 2 ]} durch die Verwendung einer Hashfunktion h , die die Elemente gleichmäßig im Hashraum (einer Binärzeichenkette der Länge L ) verteilt.

${\displaystyle h:[m]\rightarrow [0,2^{L}-1]}$

Sei bit( y,k ) das k-te Bit in der Binärdarstellung von y.

${\displaystyle y=\sum _{k\geq 0}\mathrm {bit} (y,k)*2^{k}}$

Sei die Position des niedrigstwertigen 1-Bits in der Binärdarstellung von y _i mit einer geeigneten Konvention für . ${\displaystyle \rho (y)}$${\displaystyle \rho (0)}$

${\displaystyle \rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{falls }}y>0\\L&{\text{falls }}y=0\end{cases}}}$

Sei A die Sequenz eines Datenstroms der Länge M , dessen Kardinalität bestimmt werden soll. Sei BITMAP [0... L − 1] die

Hash-Speicher, in dem die ρ ( Hashwerte ) gespeichert werden. Der folgende Algorithmus bestimmt dann die ungefähre Kardinalität von A.

Verfahrensskizze FM: für i in 0 bis L − 1 tue BITMAP[i] := 0 Ende für für x in A: tue Index := ρ(hash(x)) Wenn BITMAP[index] = 0 dann BITMAP[index] := 1 Ende wenn Ende für B := Position des am weitesten links stehenden 0-Bits von BITMAP[] return 2 ^ B 

Wenn ein Datenstrom N verschiedene Elemente enthält .

• Dann ist BITMAP [ i ] sicherlich 0 .${\displaystyle i\gg \log(N)}$
• Dann ist BITMAP [ i ] sicherlich 1 .${\displaystyle i\ll \log(N)}$
• Dann ist BITMAP [ i ] ein Rand aus Nullen und Einsen .${\displaystyle i\approx \log(N)}$

Der vorherige Algorithmus beschreibt den ersten Versuch von Flajolet und Martin, F0 im Datenstrom zu approximieren _. Ihr Algorithmus wählt eine zufällige Hashfunktion , von der sie annehmen, dass sie die Hashwerte gleichmäßig im Hashraum verteilt.

Bar-Yossef et al. führten in ^{[ 10 ]} den k-Minimum-Value-Algorithmus (KMV) zur Bestimmung der Anzahl unterschiedlicher Elemente in einem Datenstrom ein. Sie verwendeten eine ähnliche Hash-Funktion h , die auf [0,1] normalisiert werden kann . Allerdings legten sie eine Obergrenze t für die Anzahl der Werte im Hash-Raum fest. Der Wert von t wird in der Größenordnung von ε angenommen (d. h. je kleiner der Approximationswert ε ist , desto größer muss t sein ). Der KMV-Algorithmus speichert nur die t kleinsten Hash-Werte im Hash-Raum. Nachdem alle m Werte des Datenstroms eingetroffen sind, wird ε verwendet, um ε zu berechnen . Das heißt, in einem nahezu uniformen Hash-Raum erwarten sie, dass mindestens t Elemente kleiner als ε sind .${\displaystyle h:[m]\rightarrow [0,1]}$${\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}$${\displaystyle \upsilon =\mathrm {Max} (h(a_{i}))}$${\displaystyle F'_{0}={\dfrac {t}{\upsilon }}}$${\displaystyle O\left({\dfrac {t}{F_{0}}}\right)}$

Verfahren 2 K-Minimalwert Initialisiere die ersten t-Werte von KMV. für ein in a1 zu einem tun Wenn h(a) < Max(KMV) dann Entferne Max(KMV) aus der KMV-Menge Setzen Sie h(a) in KMV ein. Ende wenn Ende für return t/Max(KMV) 

Der KMV-Algorithmus kann mit einem Speicherplatz von n Bits implementiert werden . Jeder Hashwert benötigt Speicherplatz in der Ordnung n Bits. Es gibt Hashwerte der Ordnung n . Die Zugriffszeit kann reduziert werden, indem die t Hashwerte in einem Binärbaum gespeichert werden . Dadurch reduziert sich die Zeitkomplexität auf O(n²) . ${\displaystyle O\left(\left({\dfrac {1}{\varepsilon _{2}}}\right)\cdot \log(m)\right)}$${\displaystyle O(\log(m))}$${\displaystyle O\left({\dfrac {1}{\varepsilon _{2}}}\right)}$${\displaystyle O\left(\log \left({\dfrac {1}{\varepsilon }}\right)\cdot \log(m)\right)}$

Alon et al. schätzen F _k , indem sie Zufallsvariablen definieren, die innerhalb eines gegebenen Raums und einer gegebenen Zeit berechnet werden können. ^{[ 3 ]} Der Erwartungswert der Zufallsvariablen liefert den Näherungswert von F _k .

Die Länge der Sequenz m sei im Voraus bekannt. Dann konstruiere eine Zufallsvariable X wie folgt:

• Wähle ein zufälliges Element _p der Folge A mit Index an der Stelle p aus .${\displaystyle a_{p}=l\in (1,2,3,\ldots ,n)}$
• Sei die Anzahl der Vorkommen von l innerhalb der Elemente der Sequenz A, die auf ein _p folgen .${\displaystyle r=|\{q:q\geq p,a_{q}=l\}|}$
• Zufallsvariable .${\displaystyle X=m(r^{k}-(r-1)^{k})}$

Angenommen, _S₁ ist von der Ordnung n _und S₂ von der Ordnung n _. Der Algorithmus nimmt _eine Zufallsvariable S₂ und gibt den Median aus . Dabei ist Yᵢ der Mittelwert von Xᵢᵢ _, wobei 1 ≤ j ≤ S₁ _.${\displaystyle O(n^{1-1/k}/\lambda ^{2})}$${\displaystyle O(\log(1/\varepsilon ))}$${\displaystyle Y_{1},Y_{2},...,Y_{S2}}$${\displaystyle Y}$

Berechnen Sie nun den Erwartungswert der Zufallsvariablen E ( X ) .

${\displaystyle {\begin{array}{lll}E(X)&=&\sum _{i=1}^{n}\sum _{i=1}^{m_{i}}(j^{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}}}$

Aus dem oben beschriebenen Algorithmus zur Berechnung von F_{_k} geht hervor, dass jede Zufallsvariable X die Werte von a _{_p} und r speichert . Um X zu berechnen, benötigen wir daher lediglich log( n ) Bits zur Speicherung von a _{_p} und log( n ) Bits zur Speicherung von r . Die Gesamtzahl der Zufallsvariablen X beträgt ⁠ ⁠${\displaystyle S_{1}*S_{2}}$ .

Daher liegt die Gesamtspeicherkomplexität des Algorithmus in der Größenordnung von${\displaystyle O\left({\dfrac {k\log {1 \over \varepsilon }}{\lambda ^{2}}}n^{1-{1 \over k}}\left(\log n+\log m\right)\right)}$

Der vorherige Algorithmus berechnet in der Reihenfolge der Speicherbits. Alon et al. vereinfachten diesen Algorithmus in ^{[ 3 ]} mithilfe einer vierfach unabhängigen Zufallsvariablen, deren Werte auf abgebildet werden . ${\displaystyle F_{2}}$${\displaystyle O({\sqrt {n}}(\log m+\log n))}$${\displaystyle \{-1,1\}}$

Dies reduziert die Komplexität der Berechnung weiter .${\displaystyle F_{2}}$${\displaystyle O\left({\dfrac {\log {1 \over \varepsilon }}{\lambda ^{2}}}\left(\log n+\log m\right)\right)}$

Im Datenstrommodell besteht das Problem der häufigen Elemente darin, eine Menge von Elementen auszugeben, die einen bestimmten Anteil des Datenstroms überschreiten. Ein Spezialfall ist das Mehrheitsproblem , bei dem es darum geht, zu bestimmen, ob ein Wert die Mehrheit des Datenstroms darstellt.

Formaler ausgedrückt: Man wählt eine positive Konstante c > 1, die Länge des Datenstroms sei m und f _{_i} bezeichne die Häufigkeit des Wertes i im Datenstrom. Das Problem der häufigen Elemente besteht darin, die Menge { i | f _{_i} > m/c} auszugeben . ^{[ 13 ]}

Einige bemerkenswerte Algorithmen sind:

• Boyer-Moore-Mehrheitswahlalgorithmus
• Count-Min-Skizze
• Verlustbehaftetes Zählen
• Mehrstufige Bloom-Filter
• Misra-Gries-Algorithmus für Schwergewichte
• Misra–Gries-Zusammenfassung

Die Erkennung von Ereignissen in Datenströmen erfolgt häufig mithilfe eines Algorithmus zur Ermittlung der häufigsten Elemente (wie oben beschrieben): Die häufigsten Elemente und ihre Häufigkeit werden mithilfe eines dieser Algorithmen bestimmt, und der größte Anstieg gegenüber dem vorherigen Zeitpunkt wird als Trend ausgegeben. Dieser Ansatz kann durch die Verwendung exponentiell gewichteter gleitender Durchschnitte und der Varianz zur Normalisierung verfeinert werden. ^{[ 14 ]}

Das Zählen der Anzahl unterschiedlicher Elemente in einem Datenstrom (manchmal auch F_₀-Moment genannt) ist ein weiteres, gut untersuchtes Problem. Der erste Algorithmus hierfür wurde von Flajolet und Martin vorgeschlagen. Im Jahr 2010 fanden Daniel Kane , Jelani Nelson und David Woodruff einen asymptotisch optimalen Algorithmus für dieses Problem. ^{[ 15 ]} Er benötigt O ( ε² + log d ) Speicherplatz, hat Aktualisierungs- und Ausgabezeiten im schlechtesten Fall ^von O (1) und verwendet universelle Hashfunktionen sowie eine r -fach unabhängige Hashfamilie, wobei r = Ω(log(1/ ε ) / log log(1/ ε )) .

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

Ein Modell (z. B. einen Klassifikator ) durch einen einzigen Durchlauf über einen Trainingsdatensatz lernen.

• Feature-Hashing
• Stochastischer Gradientenabstieg

Für viele der untersuchten Datenstreaming-Probleme wurden untere Schranken berechnet. Die mit Abstand gebräuchlichste Methode zur Berechnung dieser unteren Schranken ist die Verwendung der Kommunikationskomplexität .

• Datenstrom-Mining
• Datenstrom-Clustering
• Online-Algorithmus
• Streamverarbeitung
• Sequentieller Algorithmus

• Alon, Noga ; Matias, Yossi ; Szegedy, Mario (1999), „Die Raumkomplexität der Approximation der Frequenzmomente“, Journal of Computer and System Sciences , 58 (1): 137–147 , doi : 10.1006/jcss.1997.1545 , ISSN  0022-0000Erstveröffentlichung: Alon, Noga; Matias, Yossi; Szegedy, Mario (1996), „The space complexity of approximating the frequency moments“, Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996) , S.  20–29 , CiteSeerX 10.1.1.131.4984 , doi : 10.1145/237814.237823 , ISBN  978-0-89791-785-8, S2CID  1627911Die
• Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev ; Widom, Jennifer (2002), „Modelle und Probleme in Datenstromsystemen“, Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) (PDF) , S.  1–16 , CiteSeerX  10.1.1.138.190 , doi : 10.1145/543613.543615 , ISBN 978-1-58113-507-7, S2CID  2071130 , archiviert vom Original (PDF) am 09.07.2017 , abgerufen am 15.07.2013Die
• Flajolet, Philippe; Martin, G. Nigel (1985). „Probabilistische Zählalgorithmen für Datenbankanwendungen“ (PDF) . Journal of Computer and System Sciences . 31 (2): 182–209 . doi : 10.1016/0022-0000(85)90041-8 . Abgerufen am 11.12.2016 .
• Gilbert, A. C .; Kotidis, Y.; Muthukrishnan, S.; Strauss, M. J. (2001), „Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries“ ( PDF) , Proceedings of the International Conference on Very Large Data Bases : 79–88Die
• Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). „Ein optimaler Algorithmus für das Problem der unterschiedlichen Elemente“. Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems . 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 .Die
• Karp, RM ; Papadimitriou, CH ; Shenker, S. (2003), „Ein einfacher Algorithmus zum Finden häufiger Elemente in Datenströmen und Datenmengen“, ACM Transactions on Database Systems , 28 (1): 51–55 , CiteSeerX  10.1.1.116.8530 , doi : 10.1145/762471.762473 , S2CID  952840Die
• Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, Jun; Zhang, Hui (2006). „Datenstreaming-Algorithmen zur Schätzung der Entropie des Netzwerkverkehrs“. Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006) . S. 145. doi : 10.1145/1140277.1140295 . hdl : 1802/2537 . ISBN 978-1-59593-319-5. S2CID  240982 .Die
• Xu, Jun (Jim) (2007), Ein Tutorial zum Netzwerkdaten-Streaming (PDF)Die
• Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., „Learning Nested Concepts With Limited Storage“, Proceedings IJCAI’91 Proceedings of the 12th international joint conference on Artificial intelligence - Volume 2, Pages 777–782, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©1991
• Morris, Robert (1978), „Zählen einer großen Anzahl von Ereignissen in kleinen Registern“, Communications of the ACM , 21 (10): 840–842 , doi : 10.1145/359619.359627 , S2CID  36226357Die