Hochdimensionale Indexierung: Formale Grundsätze und neue Ansätze

Abstract

Multimediale Dokumentenkollektionen finden in vielen IT-Bereichen zunehmende Verbreitung. Die Handhabung großer Datenbestände erfordert effiziente Suchoperationen, die es erlauben, Medienobjekte in akzeptablen Zeiten aufzufinden. Darunter fallen auch inhaltsbasierte Anfragen. Häufig werden charakteristische Ei- genschaften auf mehrdimensionale Merkmalsvektoren abgebildet, deren Distanz als ein Maß für die (Un-) Ähnlichkeit der repräsentierten Medienobjekte aufgefasst wird. Im Datenbankenkontext bilden geeignete Indexstrukturen und Suchalgorithmen die elementare Voraussetzung für eine effiziente Anfragebearbeitung. In diesem Beitrag stellen wir Ergebnisse aus [Bal04] dar und beschäftigen uns mit (1) den formalen Grundlagen hochdimensionaler Indexierung, (2) der Einführung eines adaptiven Indexierungsschemas, (3) Fragen des Index-Tunings auf der Grundlage eines analytischen Kostenmodells und (4) dem experimentellen Vergleich konkurrierender Indexierungsvorschläge. Im Vorgriff auf die folgende Darstellung dieser Beiträge ist es gelungen, eine neue Indexierungsmethode zu entwickeln, die bei der An- fragebearbeitung deutliche Kostenvorteile gegenüber bestehenden Ansätzen erzielt.