HNSW

HNSW steht für Hierarchical Navigable Small World und ist das verbreitetste Indexverfahren für die näherungsweise Vektorsuche. Es baut einen mehrschichtigen Graphen aus Nachbarschaftsverbindungen auf, in dem sich die Suche von groben zu feinen Abständen vorarbeitet. Malkov, Yashunin

Von der Übersicht ins Detail

Jeder gespeicherte Vektor ist ein Knoten und mit einigen Nachbarn verbunden. Die Zuordnung zu den Schichten erfolgt zufällig mit abnehmender Wahrscheinlichkeit, sodass die oberen Schichten dünn besetzt sind und weite Sprünge erlauben. Die Suche beginnt oben, springt in die richtige Gegend und arbeitet sich nach unten, wo die Verbindungen kurz sind. Der Aufwand wächst dadurch nur logarithmisch statt linear.

Das Verfahren stammt aus dem Jahr 2016 und steckt heute in den meisten Vektordatenbanken. In der Übersicht zu solchen Systemen zählt es zu den Standardbausteinen. Pan et al.

So kannst du dir das vorstellen

Die Suche funktioniert wie eine Reise mit umsteigen. Zuerst der Fernzug in die richtige Region, dann der Regionalzug, zuletzt der Bus in die Straße. Niemand fährt mit dem Bus quer durchs Land. Das Bild erklärt die Schichten, es beschreibt nicht den Aufbau des Index.

Was es in der Praxis bedeutet

Drei Einstellungen tauchen in jeder Konfiguration auf: wie viele Verbindungen ein Knoten bekommt, wie gründlich beim Einfügen gesucht wird und wie breit bei der Anfrage gesucht wird. Alle drei tauschen Speicher und Zeit gegen Trefferquote. Die dritte lässt sich im laufenden Betrieb ändern, die ersten beiden bestimmen den Index und erfordern einen Neuaufbau.

Zu beachten ist außerdem der Arbeitsspeicher: Der Graph liegt üblicherweise im Hauptspeicher, was bei großen Sammlungen die eigentliche Kostenfrage ist. Und das Löschen von Einträgen ist in Graphindizes unangenehm, weshalb viele Systeme zunächst nur als gelöscht markieren und später neu aufbauen.

Wo es verwechselt wird

HNSW ist ein Index, kein Ähnlichkeitsmaß: Welches Maß verwendet wird, etwa der Kosinus, wird getrennt eingestellt. Und es ist nicht das einzige Verfahren, nur das gängigste.

Verwandte Begriffe

Approximate Nearest Neighbor, Vector Database, Vector Search, Cosine Similarity, Embedding.