Grundlagen, Entwicklung und Evaluierung einer effizienten Approximationstechnik für Nearest-Neighbor-Anfragen im hochdimensionalen Vektorraum

Bei der inhaltsbasierten Suche in Multimedia-Datenbeständen, wie etwa digitalisierten Fotobeständen, findet häufig das Feature-Modell Anwendung, das charakteristische Merkmale der Medienobjekte auf numerische Feature-Werte abbildet. Die Ähnlichkeit zwischen den Medienobjekten wird beispielsweise durch eine Distanz zwischen den so aggregierten Feature-Vektoren abstrahiert. Das ähnlichste Medienobjekt innerhalb der Datenbank bezüglich eines vorzugebenen Anfrageobjektes entspricht so dem „Nächsten Nachbarn“ unter allen Feature-Vektoren. Die effiziente Anfragebearbeitung erfordert gerade in großen Medienkollektionen eine geeignete Indexunterstützung für diese hochdimensionalen Feature-Vektoren.
In der vorliegenden Arbeit wird eine Indexierungstechnik, die Active-Vertice-Methode, eingeführt, die in die Klasse der Approximationstechniken einzuordnen ist. Die Active-Vertice-Methode verfolgt ein hierarchisches Approximationsprinzip, das sich in der Lokalisierung und verschiedenen Geometrievarianten der Approximationsregionen der Datenverteilung anpasst. Auf diese Weise gelingt sowohl gegenüber etablierten Konkurrenzmethoden, als auch der Naivlösung eines sequenziellen Relationenscans eine Verbesserung der Anfrageperformanz, die analytisch und experimentell nachgewiesen wird. Darüber hinaus werden im Formalteil dieser Arbeit die stochastischen Grundlagen für die analytische Betrachtung der hochdimensionalen Nearest-Neighbor-Problematik gelegt, die später in der analytischen Kostenmodellierung der Active-Vertice-Methode Anwendung finden. Darüber hinaus bietet diese Arbeit einen Überblick und kritischen Vergleich aktueller hochdimensionaler Indexierungsansätze.