Algorithmen für Datenströme

• Applicant: Professor Dr. Christian Sohler
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 24390731

• Final Report Year: 2011

Final Report Abstract

In den letzten Jahren sind immer mehr Anwendungen entstanden, in denen große Datenmengen auftreten. So fallen beispielsweise bei der Überwachung von Netzwerkdatenverkehr, der Verarbeitung von Anfragen an Suchmaschinen oder im Bereich der Finanztransaktionen sehr große Datenmengen an, die häufig nicht in den Hauptspeicher eines Rechners passen. Daher können diese Daten mit klassischen Algorithmen in den seltensten Fällen effizient ausgewertet werden. Man benötigt spezielle Algorithmen, die die Eingabe in einem oder in wenigen Durchläufen über den Datensatz verarbeiten und nur eine kleine Zusammenfassung des gesamten Datensatzes abspeichern. Solche Algorithmen werden auch als Datenstromalgorithmen bezeichnet. Das Hauptziel des Projektes war die Entwicklung von Algorithmen zur Analyse von Datenströmen. Insbesondere haben wir uns mit dem Bereich der geometrischen Datenströme beschäftigt. Aus unserer Projektarbeit in diesem Bereich sind effiziente Clustering- und Facility-Location-Algorithmen sowie Algorithmen zur Berechnung metrischer Einbettungen hervorgegangen.

Publications

• A PTAS for k-Means Clustering Based on Weak Coresets. In: Proceedings of the 23rd Annual ACM Symposium on Computational Geometry, pp. 11–18, 2007
  D. Feldman, M. Monemizadeh, and C. Sohler
  
• StrSort Algorithms for Geometric Problems. In: Proceedings of the 23rd European Workshop on Computational Geometry (EWCG), pp. 69–72, 2007
  C. Lammersen and C. Sohler
  
• Facility Location in Dynamic Geometric Data Streams. In: Proceedings of the 16th Annual European Symposium on Algorithms (ESA), pp. 660–671, 2008
  C. Lammersen and C. Sohler
  
• d-dimensional Knapsack in the Streaming Model. In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA), pp. 468–479, 2009
  S. Ganguly and C. Sohler
  
• Streaming Embeddings with Slack. Proceedings of the 11th Workshop on Algorithms and Data Structures (WADS), pp. 483–494, 2009
  C. Lammersen, A. Sidiropoulos, and C. Sohler
  
• Approximation Techniques for Facility Location and Their Applications in Metric Embeddings. Dissertation, TU Dortmund, 2010
  C. Lammersen
  
• Information Complexity and Data Stream Algorithms for Basic Problems. Dissertation, TU Dortmund, 2010
  A. Gronemeier
  
• StreamKM++: A Clustering Algorithm for Data Streams. In: Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 175–187, 2010. ACM Journal on Experimental Algorithmics
  M. R. Ackermann, C. Lammersen, M. Märtens, C. Raupach, C. Sohler, and K. Swierkot