Hierarchische navigierbare Small-World-Graphen (HNSW) sind ein Algorithmus für die approximative Suche nach dem nächsten Nachbarn. Er wird verwendet, um Elemente zu finden, die einem Abfrageelement in einer großen Sammlung ähnlich sind, ohne das Abfrageelement mit jedem Element einzeln zu vergleichen. Der Algorithmus wird häufig für die Suche in Vektordaten verwendet, bei der Elemente wie Dokumente, Bilder, Lieder oder Benutzerprofile als Zahlenlisten, sogenannte Vektoren, dargestellt werden. Elemente mit ähnlichen Vektoren werden gemäß dem Modell, das die Vektoren erzeugt hat, als ähnlich behandelt, und HNSW bietet eine Möglichkeit, diese Vektoren schnell zu durchsuchen, insbesondere bei großen Datensätzen.
HNSW speichert Vektoren in einem Graphen. Jeder Vektor ist ein Knoten, und Verbindungen verknüpfen ihn mit einigen nahegelegenen Vektoren. Der Graph hat mehrere Ebenen: Obere Ebenen enthalten weniger Knoten und fungieren wie eine grobe Karte, während die unterste Ebene alle Knoten enthält und eine detailliertere Sicht bietet. Eine Suche beginnt in einer oberen Ebene, folgt Verbindungen zu Knoten, die näher an der Abfrage liegen, und wiederholt den Vorgang dann in unteren Ebenen, bis sie eine Menge wahrscheinlicher nächster Nachbarn findet.
Hintergrund
Das Problem der Suche nach dem nächsten Nachbarn fragt, welche Elemente in einem Datensatz am nächsten zu einem Abfrageelement liegen. Eine direkte Suche kann die Abfrage mit jedem Element im Datensatz vergleichen, aber dies wird langsam, wenn der Datensatz groß ist. Exakte Suchmethoden, die auf räumlichen Bäumen basieren, wie der k-d-Baum und der R-Baum, können bei hochdimensionalen Daten ebenfalls weniger effektiv werden, ein Problem, das oft mit dem Fluch der Dimensionalität in Verbindung gebracht wird.
Approximative Methoden zur Suche nach dem nächsten Nachbarn tauschen etwas Genauigkeit gegen Geschwindigkeit oder geringeren Ressourcenverbrauch. Anstatt immer das exakt nächste Element zu garantieren, versuchen sie, nahe Elemente schnell zurückzugeben. Andere approximative Methoden umfassen lokalitätsempfindliches Hashing und Produktquantisierung.
HNSW baut auf Forschung zu Small-World-Netzwerken und navigierbaren Graphen auf. In einem Small-World-Graphen können die meisten Knoten über eine kurze Kette von Verbindungen von anderen Knoten erreicht werden. In einem navigierbaren Graphen kann ein Suchverfahren lokale Informationen nutzen, um sich auf ein Ziel zuzubewegen. Jon Kleinbergs Arbeit zur Navigation in Small-World-Netzwerken ist ein wichtiges Beispiel für dieses Forschungsgebiet. Spätere Arbeiten untersuchten Möglichkeiten, Verbindungen hinzuzufügen, die es erleichtern, Graphen gierig zu navigieren.
Der HNSW-Algorithmus erweitert frühere navigierbare Small-World-Methoden für die Ähnlichkeitssuche, indem er eine Hierarchie von Graphebenen hinzufügt. Diese Hierarchie hilft dem Algorithmus, eine gute Region des Graphen zu finden, bevor er eine detailliertere Suche in der untersten Ebene durchführt.
Algorithmus
HNSW basiert auf einem Näherungsgraphen. In diesem Graphen sind nahegelegene Vektoren durch Kanten verbunden. Der Algorithmus nutzt diese Kanten, um sich durch den Datensatz zu bewegen, anstatt jeden Vektor zu scannen.
Der Graph ist hierarchisch. Jeder Vektor erscheint in der untersten Ebene. Einige Vektoren werden auch in höheren Ebenen platziert, wobei mit zunehmender Höhe weniger Vektoren erscheinen. Die oberen Ebenen ermöglichen Bewegungen über große Entfernungen im Datensatz, während die unteren Ebenen eine detailliertere Suche in der Nähe vielversprechender Kandidaten ermöglichen.
Eine typische Suche läuft wie folgt ab:
- Die Suche beginnt an einem Einstiegspunkt in der höchsten Ebene.
- Bei jedem Schritt betrachtet der Algorithmus benachbarte Knoten und bewegt sich zu einem Nachbarn, der näher an der Abfrage liegt.
- Wenn er in dieser Ebene keinen näheren Nachbarn finden kann, wechselt er zur nächsten Ebene.
- In der untersten Ebene untersucht er eine größere Menge von Kandidatenknoten und gibt die gefundenen nächsten Kandidaten zurück.
Diese Suchstrategie wird oft als gierige Navigation beschrieben. Der Algorithmus wählt wiederholt lokal bessere Knoten aus und nutzt die Graphenstruktur, um sich dem Abfragepunkt zu nähern.
Konstruktion und Parameter
Der HNSW-Graph wird inkrementell aufgebaut. Wenn ein neuer Vektor eingefügt wird, weist der Algorithmus ihm eine maximale Ebene zu, sucht nach nahegelegenen vorhandenen Knoten und verbindet den neuen Knoten mit ausgewählten Nachbarn in jeder Ebene, in der er erscheint.
Implementierungen legen in der Regel Parameter offen, die den Kompromiss zwischen Geschwindigkeit, Genauigkeit, Speichernutzung und Konstruktionszeit steuern. Eine höhere Anzahl von Graphverbindungen kann die Trefferquote verbessern, erfordert aber mehr Speicher. Eine größere Suchkandidatenliste kann die Genauigkeit verbessern, macht aber Abfragen langsamer. Eine größere Konstruktionskandidatenliste kann die Qualität des Graphen verbessern, macht aber den Indexaufbau langsamer.
Da HNSW approximativ ist, sind seine Ergebnisse nicht immer identisch mit einer vollständigen exakten Suche. Seine praktische Leistung hängt vom Datensatz, dem Distanzmaß, der Implementierung und den Parametereinstellungen ab. Benchmark-Studien haben gezeigt, dass HNSW-basierte Bibliotheken zu den leistungsstärksten unter den approximativen Methoden zur Suche nach dem nächsten Nachbarn gehören, obwohl die Leistung im schlechtesten Fall von der Leistung bei gängigen Benchmark-Datensätzen abweichen kann.
Verwendung in Vektorsuchsystemen
HNSW wird als Index in Systemen verwendet, die hochdimensionale Vektoren speichern und durchsuchen. Zu diesen Systemen gehören Vektordatenbanken, Suchmaschinen und Datenbankerweiterungen. Typische Anwendungen umfassen semantische Suche, Empfehlungssysteme, Bildähnlichkeitssuche und retrieval-augmentierte Generierung, die häufig in generativer KI und Large-Language-Model-Pipelines eingesetzt wird.
Mehrere Softwareprojekte implementieren oder unterstützen HNSW. Zu den Bibliotheken gehören hnswlib, das mit den ursprünglichen HNSW-Autoren verbunden ist, und FAISS. Datenbank- und Suchsysteme, die HNSW-Unterstützung dokumentieren, umfassen Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant und Redis. Diese Tools werden häufig auf Cloud-Plattformen wie Amazon Web Services, Microsoft Azure und Google Cloud für Produktions-Machine-Learning-Workloads bereitgestellt.
Siehe auch
- Approximative Suche nach dem nächsten Nachbarn
- Vektordatenbank
- Lokalitätsempfindliches Hashing
- Produktquantisierung