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 1.: Fehlende Zahl

Sei $\pi$ eine Permutation der Zahlenmenge $\{1,...,n\}$ und sei $\pi _{-1}=\pi$ 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.

Die Bestimmung dieser Zahl ist jedoch auch mit folgendem Datenstromalgorithmus möglich:

$s={\frac {n(n+1)}{2}}-\sum _{1\leq i\geq n}{i}$

Dieser Algorithmus muss offensichtlich wesentlich weniger Daten speichern und fürht schneller zum Erfolg.

Weblinks

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