Im Arbeitsbereich der Multimedia-Datenbanksysteme ist die Suche ähnlicher Objekte ein wichtiges Forschungsgebiet. Für die meisten Anwendungen in Multimedia-Datenbanken ist eine exakte Suche nicht sinnvoll. Deshalb wurde viel Mühe darauf verwendet, effiziente und effektive Methoden der Ähnlichkeitssuche zu entwickeln. Eine weit verbreitete Methode für die Implementierung der Ähnlichkeitssuche ist die auf Objekteigenschaften basierende Methode. Diese Methode transformiert alle multimediale Objekte, die in einer Datenbank gespeichert sind, in hochdimensionale Feature-Vektoren. Nach der Transformation werden diese Feature-Vektoren in einen Indexstruktur eingefügt, um so effiziente Ähnlichkeitssuchen durchzuführen.

Diese Dissertation trägt dazu bei neuartige Lösungen vorzuschlagen, indem sie erforscht wie die Effizienz der Ähnlichkeitssuche verbessert werden kann. Die Dissertation beginnt mit einer Untersuchung, wie man die Effektivität (d.h. die Qualität der Ergebnisse) der Ähnlichkeitssuche verbessern kann. Es wird aufgezeigt, dass mit Kombinationen von Feature-Vektoren die Effektivität der Ähnlichkeitssuche bedeutsam erweitert werden kann. Es werden Methoden vorgestellt, um Suchobjektsabhängig Gewichte für lineare Kombinationen von Feture-Vektoren zu berechnen, was die Effektivität der Ähnlichkeitssuche weiter verbessern kann. Das Design und die Analyse von neuen Indexstrukturen sind notwendig, um Ähnlichkeitsanfragen mit Kombinationen von Feature-Vektoren effizient durchzuführen, denn bislang können fast alle Indexstrukturen für Ähnlichkeitssuche nur individuelle Feature-Vektoren indizieren. Dies begründete die besondere Motivation, der in der restlichen Dissertation erforschten Methoden.

Im zweiten Teil der Dissertation werden verschiedene Algorithmen und Indexstrukturen vorgeschlagen, um die Effizienz der Ähnlichkeitssuche zu verbessern. Zuerst werden Techniken zur Auswahl von Pivots für Pivotbasierte Indexstrukturen untersucht. Es wird ein auf Abstandhistogramme basiertes Effizienzkriterium angeführt, um gute Pivotmenge auszuwählen und der empirische Beweis dargelegt, dass die dargebotene Methode effektiv ist. Desweiteren wird ein verbesserter k-Nächste-Nachbarn-Algorithmus dargestellt, welcher auf dem best-first Algorithmus von Hjaltason und Hamet basiert. Obwohl der ursprüngliche Algorithmus in der Abstandsberchnung optimal ist, sind seine Raumanforderungen bedeutend. Der verbesserte Algorithmus zielt auf die Absenkung der Raumanforderungen mit Hilfe von Distanzschätzfunktionen ab. Drittens wird eine metrische Indexstruktur für dynamische Kombinationen von Feature-Vektoren dargestellt. Die Indexstruktur ist Pivot-basiert und kann einen Vorteil aus den zuvor entwickelten Pivotwahlmethoden ziehen. Zum Abschluss wird eine Annäherung ausgeführt, welche auf die Minimierung der zu erwartenden Suchzeit einer Ähnlichkeitsuche zielt. Die prinzipielle Idee ist, die am häufigsten benutzteten Kombinationen von Feature-Vektoren zu indizieren. Das sich ergebende Optimierungsproblem kann zu einem Binary-Linear-Program ummodelliert werden, wenn es bei der Speicherung von Indexstrukturen Beschränkungen des Speicherplatzes gibt. Da Binary-Linear-Programs im Allgemeinen NP-hart sind, werden Algorithmen vorgeschlagen, die auf schnelle Weise gute Indexmengen finden.

Der Schlußteil der Dissertation beschreibt die Erforschung der Verwendung von Grafikkartenprozessoren (GPU) für die Beschleunigung von Datenbankoperationen. Es werden GPU-Implementierungen für hoch-dimensionale Nächste-Nachbarn-Suche und ein Clusteringalgorithmus vorgestellt. Die experimentelle Evaluierung zeigt, dass die vorgestellte GPU-basierten Algorithmen eine Größenordnung schneller sind als die gleichen aus CPU-basierenden Algorithmen.

An important research issue in the field of multimedia databases is the retrieval of similar objects. For most applications in multimedia databases, an exact search is not meaningful. Thus, much effort has been devoted to develop efficient and effective similarity search techniques. A widely used approach for implementing similarity search engines is the feature-based approach. In this approach, all multimedia objects stored in a database are transformed into high-dimensional feature vectors, which are then inserted into an index structure to efficiently perform similarity queries.

The contribution of this thesis is to explore and propose novel solutions to improve the efficiency of similarity queries in multimedia databases. The thesis begins with a study on how to improve the effectiveness (i.e., the quality of the answer) of a similarity retrieval engine. We first show that by using combinations of feature vectors the effectiveness of the similarity search may be significantly enhanced. Then, we describe methods for computing query-dependent weights to perform linear combinations of feature vectors, which can further improve the effectiveness of the similarity search. As almost all index structures for similarity search developed so far can only deal with single feature vectors, the design and analysis of new index structures is necessary to efficiently perform similarity queries that use combinations of feature vectors. This gives an extra motivation for the techniques studied in the rest of the thesis.

In the next part of the thesis, we propose several algorithms and index structures to improve the efficiency of similarity queries. Firstly, we study pivot selection techniques for pivot-based indices. We provide an efficiency criterion based on distance histograms for selecting good set of pivots, and present empirical evidence showing that the technique is effective. Secondly, we describe an improved k nearest neighbor (k-NN) algorithm, which is based on the best-first traversal algorithm proposed by Hjaltason and Samet. Although the original algorithm is already optimal in the number of distance computations, its space requirements are significant. The improved algorithm aims to lower the space requirements by using distance estimators. Thirdly, we present a metric access method for dynamic combinations of feature vectors. The index is pivot-based, and it can take advantage of the previously studied pivot selection techniques. Finally, we introduce an approach that aims to minimize the expected search cost of a similarity query. The idea is to index only the most frequently used combinations of feature vectors. If there are restrictions on the available space for constructing indices, then the resulting optimization problem can be modeled as a binary linear program. As binary linear programs are NP-hard in the general case, we also propose algorithms that quickly find good sets of indices.

The last part of the thesis explores the use of graphics processor units (GPUs) for accelerating database operations. We present GPU implementations of a high-dimensional nearest neighbor search and a clustering algorithm. An experimental evaluation shows that the proposed GPU algorithms are an order of magnitude faster than their CPU versions.