Textdokument
Algorithms for dynamic geometric data streams
Lade...
Volltext URI
Dokumententyp
Zusatzinformation
Datum
2007
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Die zunehmende Vernetzung moderner Computersysteme produziert gewaltige Datenmengen, deren Behandlung die heutige Informatik vor unzählige Probleme stellt. Traditionelle Algorithmen, deren Laufzeit zu stark von der Größe der Daten abhängt, sind häufig nicht anwendbar. Oft sind die Eingabedaten sogar zu groß für die verfügbaren Speichermedien. Wir stellen neue, grundlegende Algorithmen zur Analyse gewaltiger Datenmengen vor, die unter minimalen Anforderungen an den Speicher der Computersysteme beweisbar gute Zusammenfassungen der Daten berechnen. Zunächst erarbeiten wir grundlegende Ergebnisse zum Ziehen von Stichproben aus dynamischen Datenströmen. Mit Hilfe dieser Stichproben können vielfältige Aussagen über die Eingabedaten getroffen werden, was wir anhand von Beispielen beweisen. Anschließend wenden wir uns dem Clustering gewaltiger Datensätze zu. Wir entwickeln eine Methode, große Datenmengen zu sogenannten Coresets zusammenzufassen. Die Methode erzeugt beweisbar k-meansund k-median-Clusterings mit beliebig guter Approximationsgarantie und ist anwendbar in vielen verschiedenen Modellen: Die Clusterings können mit wenig Speicher für dynamische Datenströme berechnet werden, sie lassen sich in sublinearer Zeit durch Bereichsanfragen erstellen, und auch sich bewegende Punkte können effizient zusammengefasst werden. Eine Implementierung zeigt, dass die Methode auf großen realen Testdaten gute Clusterings deutlich schneller berechnen kann als häufig angewendete traditionelle Algorithmen. Schließlich beschäftigen wir uns mit der Analyse der Struktur von großen Graphen wie dem Webgraph. Wir entwickeln neue Methoden, um die Anzahl von Teilgraphen (z.B. Dreiecken) eines Graphen zu zählen, der als Datenstrom von Kanten gegeben ist.