Algorithmen für Datenströme

• Antragsteller: Professor Dr. Christian Sohler
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2006 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 24390731

Durch die stark verbesserte Übertragungskapazitä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. 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. 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. Wir interessieren uns dabei im wesentlichen für die drei Themenbereiche Clustering in Datenströmen, Analyse großer Graphen, und geometrische Datenströme. Wir wollen beispielsweise Datenstromalgorithmen für projektives Clustering entwickeln, den Clustering Koeffizient von großen Graphen bestimmen, und die bekannten offenen Probleme im Bereich dynamischer geometrischer Datenströme bearbeiten.

• DFG-Verfahren: Sachbeihilfen