Ziele

Durch die stark verbesserte Übertragunskapazität moderner Kommunikationsnetzwerke sehen wir uns immer häufiger mir sehr großen Datenmengen konfrontiert, die in der Form von Datenströmen auftreten. Typische Beispiele für Datenströme sind Netzwerkverkehr, Sensordaten oder Webcrawls. So galt z.B. vor wenigen Jahren die Gesamtanzahl an Kreditkartentransaktionen pro Monat als eine sehr große Datenmenge. Diese Menge ist vergleichbar mit der Anzahl von Datenpaketen, die ein einzelner Router über eine einzelne Schnittstelle in einer Stunde verschickt. Heutzutage möchte man aber den Datenverkehr für ein Netzwerk von vielen Routern mit vielen Schnittstellen analysieren.

Die dabei anfallenden Daten können mit klassischen Algorithmen in den seltensten Fällen effizient bearbeitet werden, da man sie wegen ihrer Größe kaum oder gar nicht speichern kann und ein freier Zugriff auf die abgespeicherten Daten sowieso viel zu zeitintensiv wäre. Man benötigt daher Algorithmen, die die Eingabe in einem oder in wenigen Durchläufen über den Datensatz verarbeiten können und die weniger Speicherplatz benötigen, als der Datensatz selbst. Solche Algorithmen werden auch als Datenstromalgorithmen bezeichnet.

Ziel dieses Projektes ist die Entwicklung von Algorithmen zur Analyse von Datenströmen. Dabei teilt sich unser Projekt in drei Teilbereiche auf:

• Clustering und Facility Location in Datenströmen
• Analyse großer Graphen (Webcrawls, etc.)
• Algorithmen für geometrische Datenströme

Unter Clustering versteht man die Partitionierung einer Datenmenge in Mengen (sogenannte Cluster), so dass alle Datensätze eines Clusters ähnlich sind, Datensätze in unterschiedlichen Clustern sich aber deutlich unterscheiden. Eine solche Partitionierung gibt die Struktur der Datenmenge wieder und kann so zur Reduzierung des Datenvolumens dienen (z.B. könnte man jeden Cluster durch einen Datensatz des Clusters darstellen). Damit ist Clustering ein wichtiges Werkzeug bei der Analyse von Datenströmen.

Bei der Analyse großer Graphen möchten wir Kennzahlen wie den sogenannten Clustering Coefficient bestimmen, der eng mit der Anzahl der Dreiecke in einem Graphen zusammenhängt. Wir interessieren uns außerdem für die Struktur von Co-Citation Graphen. Ein Co-Citation Graph für einen gerichteten Graph G enthält genau dann eine Kante zwischen Knoten u und v, wenn es in G einen Knoten w gibt mit gerichteten Kanten nach u und v. Wir gehen dabei davon aus, dass wir den gerichteten Graph als Datenstrom bekommen.

Im dritten Teilbereich wollen wir uns mit den bekannten offenen Fragen im Bereich der dynamischen geometrischen Datenströme (Matching, bichromatic Matching, etc.) beschäftigen. Außerdem interessieren wir uns für eine weiter vertiefte Untersuchung des Datenstrommodells mit Sortierungsoperator im Hinblick auf geometrische Probleme.

Das Projekt begann mit Christian Sohler in Paderborn und wird von ihm derzeit an der Universität Dortmund fortgeführt.

Personen

• Christian Sohler (Projektleiter, ehemals Universität Paderborn, jetzt Universität Dortmund)
• Christiane Lammersen (ehemals Universität Paderborn, jetzt Universität Dortmund)
• Morteza Monemizahdeh (ehemals Universität Paderborn, jetzt Universität Dortmund)

Publikationen zu diesem Projekt