Datenstromalgorithmen

In der Informatik ist ein Datenstromalgorithmus ein Algorithmus, der die Daten eines oder mehrerer Datenströmes sequenziell liest und dabei direkt („online“) verarbeitet.

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.

Mathematische Sichtweise und Effizienzanforderungen

Man modelliert die kontinuierlich anfallenden Daten als Strom - eine Folge von Eingabezeichen, deren Länge häufig unbekannt ist, aber als sehr groß angenommen wird.

Ein den Strom verarbeitender Algorithmus darf nur Zeichen für Zeichen des Stromes lesen, wahlfreier Zugriff (random access), d.h. ein "Springen" auf den Eingabezeichen, ist nicht erlaubt.

Im Datenstromszenario werden wegen der Menge der anfallenden Daten im Wesentlichen zwei Effizienzforderungen gestellt: Die Speicherplatzkomplexität des Datenstromalgorithmus soll sublinear, idealerweise logarithmisch oder polylogarithmisch sein, ebenso wie die Rechenzeit pro Eingabezeichen.

Gewisse Probleme lassen sich also mit Datenstromalgorithmen exakt lösen, da die gesamte Eingabe gelesen werden darf. Trotzdem sind sublinearer Speicherplatz und sublineare Rechenzeit pro Eingabezeichen Effizienzanforderungen, die häufig dazu führen, dass dies eben nicht möglich ist und nur approximative Lösungen gegeben werden können und Randomisierung eingesetzt werden muss.

Denn ein Datenstromalgorithmus darf wegen des nur sublinearen Speicherplatzes nicht die gesamte Eingabe speichern, sondern nur eine Zusammenfassung des bisher Gesehenen. Man sagt, der Algorithmus speichert eine Skizze (Sketch) der bisher gesehenen Eingabe.

Im folgenden Beispiel wird ein Algorithmus vorgestellt, der das gegebene Problem exakt lösen kann.

Beispiele

Anzahl der Elemente

Die Anzahl der Elemente in einem Datenstrom kann einfach mit einem Zähler ermittelt werden. Mit randomisierten Algorithmen lässt sich der Speicherbedarf dabei weiter verringern.

Fehlende Zahl

Sei π 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 Performanz zu erreichen, müssten dabei diese Daten im Arbeitsspeicher abgelegt werden, doch dies ist aufgrund 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 verlangsamt.

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 π, so kann man nach Lesen der gesamten Eingabe 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 der Speicherplatz beträgt damit nur O(log n). Er ist damit ganz offensichtlich effizienter.

Siehe auch

• Platzkomplexität

Literatur

• Martin Sauerhoff: Spezialvorlesung Datenstromalgorithmen. 2004/2005 (Skript)

Weblinks

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