Herr Dr. Christian Sohler,

        Fachbereich Mathematik und Informatik,

        Universität Paderborn

hält am  

        Dienstag, den 13.12.2005 um 16 Uhr s.t.

        im Raum KI/II (über dem Labsaal)

einen Vortrag mit dem Titel

Zusammenfassung:

In den letzten Jahren sehen wir uns immer häufiger mit extrem großen Datenmengen konfrontiert. Beispiele für sehr grosse Datensätze sind der Webgraph, Statistiken ueber Netzwerkdatenverkehr, die menschliche DNA oder Satellitenaufnahmen der Erdoberfläche.

Um solche Datensätze zu analysieren sind selbst klassische Linearzeitalgorithmen zu langsam und/oder zu speicherintensiv. Man benötigt spezielle Algorithmen, die die Daten z.B. mit Hilfe von zufälligen Stichproben analysieren. Solche Algorithmen werden auch sublineare Algorithmen genannt, da ihre Laufzeit und/oder ihr Speicherbedarf sublinear in der Eingabegröße ist.

In diesem Vortrag werde ich am Beispiel des k-means Clustering Problems eine Einführung in das Gebiet der sublinearen Algorithmen geben. Dabei werde ich zwei für dieses Gebiet wichtige Konzepte vorstellen und diese anhand des k-Means Clustering Problems erläutern, nämlich 'zufällige Stichproben' und 'Kernmengen'. Abschließend werde ich eine effiziente Implementierung des k-means Algorithmus für niedrigdimensionale Datenmengen vorstellen, die auf dem Einsatz von Kernmengen basiert.