Advanced Indexing and Query Processing for Multidimensional Databases

Eine weit verbreitete Technik in vielen neuen Anwendungen, wie z. B. Multimedia Datenbanken, ist die sogenannte Feature-Transformation, bei der wichtige Eigenschaften der Datenobjekte in Punkte eines mehrdimensionalen Vektorraums, die sogenannten Feature-Vektoren überführt werden. Die Suche nach 'ähnlichen' oder 'nicht-dominierten' Objekten, die auf diesen Feature-Vektoren basieren ist realisiert als Suche nach Punkten in diesem mehrdimensionalen Vektorraum. Damit eine effiziente Anfragebearbeitung in diesen hoch-dimensionalen Datenbanken unterstützt werden kann, sind hoch-dimensionale Indexstrukturen notwendig, die den Suchraum beschränken, und es müssen effiziente Anfragebearbeitungsstrategien, die diese Indexe verwenden, entwickelt werden. Ausgehend von einer Analyse der typischen hochentwickelten Datenbanksysteme, wie Multimedia-Datenbanksysteme, elektronische Marktplätze, und Entscheidungsunterstützungssysteme, werden die folgenden vier grundlegenden Charakteristika festgestellt: hoch-dimensionale Natur der Daten, Wiederverwendbarkeit von existierenden Indexstrukturen, neue (ausdrucksstärkere) Anfragetypen für Nicht-Standard-Datenbanksysteme, und effiziente Analyse von komplexen hoch-dimensionalen Daten. Das Hauptziel der vorliegenden Arbeit ist deshalb die Verbesserung der Performanz bei der indexbasierten Anfragebearbeitung in hochdimensionalen Datenräumen und die Entwicklung neuer Anfrageoperatoren. Der erste Teil der Arbeit beschäftigt sich mit Methoden der Ähnlichkeitssuche. Wir präsentieren eine neue Indexierungstechnik für mehrdimensionalen Daten, die besonders geeignet ist für die inkrementelle Bearbeitung von Nächste-Nachbar (NN) Anfragen. Die Daten werden zuerst in mehreren niedrig-dimensionalen Räumen verteilt und dann mit mehrdimensionalen Standard-Indexstrukturen indexiert. Damit wir inkrementelle NN-Anfragen effizient unterstützen können, wird zuerst ein Algorithmus entwickelt, der verantwortlich ist für das Verschmelzen von Resultaten der verschiedene Indexe. Danach wird ein Kostenmodel präsentiert, das auf dem Prinzip 'power-law' basiert und die Anzahl der Indexe voraussagt. Ein neuer Algorithmus wird vorgeschlagen, der die Dimensionen auf die verschiedenen Indexe verteilt. Weiterhin wird eine Generalisierung der 'state-of-the-art' iDistance-Technik präsentiert, die Multidimensional iDistance (MiD) genannt wird. Die Daten werden zuerst in Cluster verteilt und ein Referenzpunkt für jedes Cluster definiert. Dann wird jedes Datenobjekt in einen m-dimensionalen Distanzvektor Überführt (generel gilt m > 1). Diese m dimensionen werden generiert, indem man den originalen Datenraum in m Unterräume verteilt und die partiellen Distanzen zwischen den Objekten und den Referenzpunkten für jeden Unterraum kalkuliert. Die m-dimensionalen Punkte werden dann mit herkömlichen mehrdimensionalen Indexstrukturen indexiert. Ein Kostenmodel wird für die Berechnung des Parameters m verwendet. Effiziente Algorithmen für Bereichs- und Nächste Nachbarn- Anfragen werden zudem präsentiert. Der zweite Teil der Arbeit befasst sich mit Skyline Anfragebearbeitungstechniken: Zuerst wird das Konzept von Constrained Subspace Skyline Anfragen (CSSA) definiert. Danach, präsentieren wir einen Algorithmus für die Anfragebearbeitung, der auf mehreren niedrig-dimensionale Indexstrukturen basiert. Da wir niedrig-dimensionale Standard-Indexstrukturen benutzen, können Constrained Subspace Skyline Anfragen effizient unterstützt werden. Weiterhin werden Strategien zur Beschränkung des Suchraums entwickelt. Ein sehr wichtiger Bestandteil unserer Technik ist die workload-adaptive Strategie zur Bestimmung der passenden Anzahl der Indexe und der Zuteilung der Dimensionen zu den Indexen. Weiterhin definieren wir das Konzept von Reverse Skyline Anfragen (RSA). Für einen gegebenen Datensatz P und einen Anfragepunkt q liefert RSA die Punkte, die den Anfragepunkt als Teil der 'dynamischen' Skyline haben. Diese dynamische Skyline wird generiert, indem man alle Punkte bezüglich der Distanz zu einem Referenzpunkt transformiert. Wir präsentieren einen Branch-and-Bound-Algorithmus (BBRS Algorithmus) für Reverse Skyline Anfragen. Damit die Kosten für die Berechnung der Reverse Skyline sinken, präsentieren wir zusätzlich einen verbesserten Ansatz (RSSA Algorithmus), der auf vorberechnete Approximationen von Skylines basiert. Diese Approximationen werden benutzt, um zu entscheiden, ob ein Punkt in die Reverse Skyline gehört oder nicht. Effizienz und Effektivität aller vorgeschlagenen Verfahren werden ausführlich diskutiert und durch experimentelle Vergleiche mit herkömmlichen Methoden auf Daten aus realen Anwendungen verifiziert.