Lehr- und Forschungseinheit für Datenbanksysteme
Datenbanksysteme
Database Systems

Diplomarbeit :
Entwicklung und Evaluation einer Indexstruktur zur effizienten Ähnlichkeitssuche auf Vektormengen

Im Bereich Verwaltung und Anfragebearbeitung von komplexen Datenobjekten wie CAD-Bauteilen, Molekülen oder Web Sites ist die effiziente Berarbeitung von Ähnlichkeitsanfragen eine zentrales Aufgabengebiet. Desweiteren sind Ähnlichkeitsanfragen Kernoperationen von leistungsstarken Data Mining Techniken, wie dem dichtebasierten Clustering (DB-Scan, OPTICS) oder der KNN-Klassifikation. Die Bearbeitung läuft dabei meist in mehreren Schritten ab. Zunächst wird das Datenobjekt bezüglich bestimmter Eigenschaften in eine neue Representation überführt, die sogenannte Feature-Repräsentation. Anschließend werden die Feature-Repräsentationen in speziellen Indexstrukuren verwaltet, um effizientes Einfügen, Löschen und Anfragen zu ermöglichen. Die verbreitetste Feature-Repräsentation ist das Abspeichern aller auftretenden Merkmale in einem Featurevektor. Daher existieren für die Anfragebearbeitung auf hochdimensionalen Featurevektoren bereits einige etablierte Indexsturkturen, wie der R*-Tree, der X-Tree oder der IQ-Tree, die selbst noch in hochdimensionalen Datenräumen effizientes Anfragen ermöglichen.

Besteht ein Objekt  aber aus einer Menge von Unterobjekten, die alle im selben Vektorraum liegen, ist die Darstellung  durch einen einzelnen Featurevektor häufig unvorteilhaft. Daher is es sinnvoll mengenartige Objekte nicht als einzelne Featurevektoren, sondern als Mengen niedrig dimensionaler Vektoren zu repräsentieren.  Auf diesen Vektormengen sind bereits unterschiedliche Ähnlichkeitsmaße definiert worden, die zum Teil Metriken sind. Die effiziente Unterstützung  von Ähnlichkeitsanfragen bezüglich dieser Metriken ist allerding noch weitgehend unerforscht.

Ziel der Diplomarbeit:
Ziel der Arbeit ist es Algorithmen zur effizienten Anfragebearbeitung in Datenmengen,  mengenartiger Objekte zu  entwickeln. Von den entwickelten Verfahren soll dabei ein Prototyp erstellt werden, der anschließend auf  realen Testdaten evaluiert werden soll.
gewünschte Vorkenntnisse

Ansprechpartner

Matthias Schubert Raum : E 1.09 
Telefon : +49-89-2180-9328
Mail : schubert@dbs.informatik.uni-muenchen.de
Homepages: DBSInstitutLMU
14.06.02 Matthias Schubert