Approximate Nearest Neighbor

Approximate Nearest Neighbor, abgekürzt ANN, bezeichnet Verfahren, die zu einem gesuchten Vektor die nächsten Nachbarn finden, ohne alle gespeicherten Vektoren zu prüfen. Sie liefern meist, aber nicht immer, dieselben Treffer wie der vollständige Vergleich und sind dafür um Größenordnungen schneller.

Der Tausch heißt Trefferquote gegen Zeit

Der vollständige Vergleich skaliert schlecht, weil jeder einzelne Vergleich Rechenzeit kostet und die Vektoren groß sind. Beides zählt zu den Kernproblemen der Vektorverwaltung. Pan et al.

Näherungsverfahren bauen deshalb vorab einen Index, der den Raum grob ordnet, und durchsuchen davon nur einen Teil. Wie viel sie prüfen, ist einstellbar. Diese Einstellung bestimmt zugleich, welcher Anteil der wirklich nächsten Nachbarn gefunden wird, und dieser Anteil ist eine Messgröße, die sich vergleichen lässt.

So kannst du dir das vorstellen

Du suchst die nächste Tankstelle. Alle Entfernungen im Land nachzurechnen ist genau und dauert. Im eigenen Stadtteil nachzusehen geht sofort und liegt fast immer richtig. Nur wenn die nächste Tankstelle knapp hinter der Stadtteilgrenze steht, findest du sie so nicht. Das Bild erklärt den Kompromiss, es beschreibt kein bestimmtes Verfahren.

Was es in der Praxis bedeutet

Für die meisten Anwendungen ist die Näherung richtig, weil ein übersehener Treffer auf Platz sieben niemandem auffällt. Anders ist es bei Aufgaben, die Vollständigkeit verlangen, etwa dem Erkennen von Duplikaten oder rechtlich relevanten Recherchen. Dort gehört geprüft, ob der exakte Vergleich noch bezahlbar ist.

Beim Einrichten lohnt es sich, die Einstellung nicht blind zu übernehmen. Ein Index, der auf Geschwindigkeit getrimmt ist, findet in einem fachlich engen Bestand spürbar weniger, und die fehlenden Treffer tauchen nirgends als Fehler auf. Sichtbar wird das nur, wenn du gegen eine exakte Suche vergleichst.

Wo es verwechselt wird

Näherungsweise heißt nicht ungenau im Ergebnis: Die Abstände werden korrekt berechnet, nur eben nicht für alle Kandidaten. Und ANN ist die Aufgabenstellung, HNSW eines der Verfahren dafür. Malkov, Yashunin

Verwandte Begriffe

HNSW, Vector Search, Vector Database, Cosine Similarity, Retrieval Top-k.