Publikationsserver der Universitätsbibliothek Marburg

Titel:Advanced Indexing and Query Processing for Multidimensional Databases
Autor:Dellis, Evangelos
Weitere Beteiligte: Seeger, Bernhard (Prof. Dr.)
Veröffentlicht:2007
URI:http://archiv.ub.uni-marburg.de/diss/z2007/0676
URN: urn:nbn:de:hebis:04-z2007-06760
DOI: https://doi.org/10.17192/z2007.0676
DDC: Informatik
Titel(trans.):Advanced Indexing und Query Processing für MultidimensionaleDatenbanken
Publikationsdatum (Online):2007-10-29

Dokument

Schlagwörter:
Multi-criteria Decision Making, Pareto-Optimum, Indizierung, Nearest Neighbor Problem, Fractal Dimension, Skyline Queries, Fraktale Dimension, Query Processing, Indexing, Änlichkeitssuche, Similarity Search, Abfrageverarbeitung, Nächste-Nachbarn-Problem

Summary:
Many new applications, such as multimedia databases, employ the so-called feature transformation which transforms important features or properties of data objects into high-dimensional points. Searching for 'similar' or 'non-dominated' objects based on these features is thus a search of points in this feature space. To support efficient query processing in these high dimensional databases, high-dimensional indexes are required to prune the search space and efficient query processing strategies employing these indexes have to be designed. Based on an analysis of typical advanced database systems - such as multimedia databases, electronic market places, and decision support systems - the following four challenging characteristics of complexity are detected: high-dimensionality nature of data, re-usability of existing index structures, novel (more expressive) query operators for advanced database systems and efficient analysis of complex high-dimensional data. Therefore, the general goal of this thesis is the improvement of the efficiency of index based query processing in high-dimensional data spaces and the development of novel query operators. The first part of this thesis deals with similarity query processing techniques. We introduce a new approach to indexing multidimensional data that is particularly suitable for the efficient incremental processing of nearest neighbor queries. The basic idea is to split the data space vertically into multiple low- and medium-dimensional data spaces. The data from each of these lower-dimensional subspaces is organized by using a standard multi-dimensional index structure. In order to perform incremental NN-queries on top of index-striping efficiently, we first develop an algorithm for merging the results received from the underlying indexes. Then, an accurate cost model relying on a power law is presented that determines an appropriate number of indexes. Moreover, we consider the problem of dimension assignment, where each dimension is assigned to a lower-dimensional subspace, such that the cost of nearest neighbor queries is minimized. Furthermore, a generalization of the iDistance technique, called Multidimensional iDistance (MiD), for k nearest neighbor query processing is presented. Three main steps are performed for building MiD. In agreement with iDistance, firstly, data points are partitioned into clusters and, secondly, a reference point is determined for every cluster. However, the third step substantially differs from iDistance as a data object is mapped to a m-dimensional distance vector where m > 1 generally holds. The m dimensions are generated by splitting the original data space into m subspaces and computing the partial distance between the object and the reference point for every subspace. The resulting m-dimensional points can be indexed by an arbitrary point access method like an R-tree. Our crucial parameter m is derived from a cost model that is based on a power law. We present range and k-NN query processing algorithms for MiD. The second part of this thesis deals with skyline query processing techniques. We first introduce the problem of Constrained Subspace Skyline Queries (CSSQ). We present a query processing algorithm which builds on multiple low-dimensional index structures. Due to the usage of well performing low dimensional indices, constrained subspace skyline queries for arbitrary large subspaces are efficiently supported. Effective pruning strategies are applied to discard points from dominated regions. An important ingredient of our approach is the workload-adaptive strategy for determining the number of indexes and the assignment of dimensions to the indexes. Furthermore, we introduce the concept of Reverse Skyline Queries (RSQ). Given a set of data points P and a query point q, an RSQ returns the data objects that have the query object in the set of their 'dynamic' skyline. Such kind of dynamic skyline corresponds to the skyline of a transformed data space where point q becomes the origin and all points are represented by their distance to q.In order to compute the reverse skyline of an arbitrary query point, we first propose a Branch and Bound algorithm (called BBRS), which is an improved customization of the original BBS algorithm. To reduce even more the computational cost of determining if a point belongs to the reverse skyline, we propose an enhanced algorithm (called RSSA), that is based on accurate pre-computed approximations of the skylines. These approximations are used to identify whether a point belongs to the reverse skyline or not. The effectiveness and efficiency of all proposed techniques are discussed and verified by comparison with conventional approaches in versatile experimental evaluations on real-world datasets.

Zusammenfassung:
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.


* Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten