Approximate-Nearest-Neighbor Search

Objekte in Multimediadatenbanken werden häufig durch Featurevektoren repräsentiert. So kann beispielsweise das Farbhistogramm eines Bildes als Featurevektor dargestellt werden, wobei jede Dimension des Vektors einem Bin des Histogramms entspricht. Nutzer solcher Datenbanken wollen vor allem wissen "welche Objekte sind zu meiner Anfrage am ähnlichsten". Es stellt sich heraus, dass alle bekannten Indexstrukturen mit steigender Dimension der Featurevektoren solche Anfragen nicht wesentlich effizienter beantworten können, als jedes einzelne Objekt mit der Anfrage zu vergleichen.

Ein neuer Ansatz um dem "Curse of Dimensionality" entgegenzuwirken sind Approximate-Nearest-Neighbor Indexstrukturen. Sie werden in Anwendungsszenarien eingesetzt, bei denen eine "gute" statt der exakten Antwort auf Nächste-Nachbar-Anfragen genügt. Den Verlust von Genauigkeit kompensieren Sie allerdings mit einem extremen Laufzeitgewinn.

Es ergeben sich hier mehrere Arbeiten, welche sich mit dem ANN-Problem auseinandersetzen, u.a.:

• Entwicklung eines generisches Framework zur Evaluierung von ANN-Indexstrukturen
• Implementierung und Evaluierung gängiger ANN-Indexstrukturen
• Erweiterung von bekannten Strukturen um auch andere Anfragetypen effizient zu unterstützen (Inkrementelles Ranking, Bereichsanfragen,…)