Datenstromalgorithmus

Die Informatik bezeichnet mit Datenstromalgorithmus einen Algorithmus, der die Daten eines Datenstroms sequenziell bearbeitet und dabei nur eine kleine Zusammenfassung speichert.

Anwendung

Viele heutige Anwendungen in der Informatik machen auf Grund der extrem großen, kontinuierlich angelieferten Datenmenge, die Verarbeitung eines Datenstroms erforderlich. Dies ist beispielsweise bei der Erfassung von Routingdaten in Netzwerken, bei Aufzeichnungen von Telekommunikationsdaten, bei Banktransaktionen oder bei Börsentickern der Fall. Die dort anfallenden Daten haben kein Ende und müssen deshalb sequentiell ausgewertet werden. Auch ist die Datenmenge zumeist so hoch, dass sie von nicht auf ein Mal ausgewertet werden könnte.

Beispiel: Fehlende Zahl

Sei $\pi$ eine Permutation der Zahlenmenge $\{1,...,n\}$ mit einem fehlenden Element $s$.

Ein einfache Methode zur Bestimmung der fehlendes Zahl wäre, alle Zahlen zu sammeln, zu sortieren und diese geordnete Menge dann der Reihe nach auf das fehlende Element zu durchsuchen. Dazu müssten aber wie beschrieben alle Zahlen gespeichert werden. Der Speicherverbrauch dieses Algorithmus beträgt dann $n*4$ Bytes, wenn angenommen wird, das jede Zahl als 32-Bit Integer gespeichert wird. So müsste man bspw. für $n=1.000.000.000$ ca. 3,7 GB Speichern. Um eine angemessene Performance zu erreichen müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist auf Grud des großen Datenvolumens bei den meisten PCs nicht möglich. Somit müsste auf die Festplatte zurückgegriffen werden, was jedoch diesen Algorithmus extrem verlangsammt.

Wären alle Zahlen $1,...,n$ im Datenstrom enthalten, so wäre die Summe der Elemente des Stromes gemäß der Gaußsche Summenformel $\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$. Bildet man daher die Summe der im Strom enthaltenen $n-1$ Elemente in $\pi$, so kann man danach die gesuchte Zahl $s$ mit $s={\frac {n(n+1)}{2}}-\sum {\pi }$ bestimmen. Dieser Algorithmus muss zur Berechnung der Summe und zur anschließenden Bestimmung von $s$ nur eine Zahl speichern und ist damit ganz offensichtlich effizienter.

Siehe auch

• Platzkomplexität

Weblinks

"Data Streams: Algorithms and Applications" von S. Muthukrishnan (Postscript)