Logo des Repositoriums
 
Textdokument

Algorithms for dynamic geometric data streams

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2007

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.

Beschreibung

Frahling, Gereon (2007): Algorithms for dynamic geometric data streams. Ausgezeichnete Informatikdissertationen 2006. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-411-0. pp. 49-58

Schlagwörter

Zitierform

DOI

Tags