HNSWLib ist eine reine Header-Header-Bibliothek in C++, die den Hierarchical Navigable Small World (HNSW)-Algorithmus für die approximative Suche nach nächsten Nachbarn implementiert. Die Bibliothek wurde entwickelt, um in großen Sammlungen von Vektordaten Elemente zu finden, die einem Abfrageelement ähnlich sind, ohne das Abfrageelement mit jedem Element einzeln zu vergleichen. Sie wird häufig in Maschinelles-Lernen-Systemen, Künstliche-Intelligenz-Anwendungen und Vektordatenbanken eingesetzt, wo Geschwindigkeit und Skalierbarkeit entscheidend sind.
Der HNSW-Algorithmus, den HNSWLib implementiert, speichert Vektoren in einer mehrschichtigen Graphenstruktur. Jeder Vektor wird zu einem Knoten, und Verbindungen verknüpfen ihn mit nahegelegenen Vektoren. Obere Schichten enthalten weniger Knoten und dienen als grobe Karte, während die unterste Schicht alle Knoten für die detaillierte Suche enthält. Eine Suche beginnt in einer oberen Schicht, folgt Verbindungen zu Knoten, die näher an der Abfrage liegen, und wiederholt den Prozess in unteren Schichten, bis sie eine Menge wahrscheinlicher nächster Nachbarn identifiziert.
Hintergrund
Das Problem der Suche nach nächsten Nachbarn fragt, welche Elemente in einem Datensatz einem Abfrageelement am nächsten liegen. Eine direkte Suche vergleicht die Abfrage mit jedem Element, was bei großen Datensätzen langsam wird. Exakte Methoden, die räumliche Bäume wie den k-d-Baum oder R-Baum verwenden, verlieren bei hochdimensionalen Daten aufgrund des Fluchs der Dimensionalität an Effektivität. Approximative Methoden für nächste Nachbarn tauschen Genauigkeit gegen Geschwindigkeit, indem sie nahe Elemente schnell zurückgeben, anstatt das absolut nächste zu garantieren.
HNSW baut auf Forschung zu Small-World-Netzwerken und navigierbaren Graphen auf. In Small-World-Graphen sind die meisten Knoten über kurze Verbindungsketten verbunden. Jon Kleinbergs Arbeit zur Navigation in Small-World-Netzwerken beeinflusste spätere Forschung zur Hinzufügung von Verbindungen, die Graphen leichter gierig navigierbar machen. Der HNSW-Algorithmus erweitert frühere navigierbare Small-World-Methoden um eine Hierarchie von Graphenschichten, die hilft, eine gute Region zu finden, bevor eine detaillierte Suche erfolgt.
Algorithmus
HNSWLib verwendet einen Näherungsgraphen, in dem nahegelegene Vektoren durch Kanten verbunden sind. Der Algorithmus bewegt sich durch den Datensatz über diese Kanten, anstatt jeden Vektor zu scannen. Der Graph ist hierarchisch: Jeder Vektor erscheint in der untersten Schicht, während einige Vektoren auch in höheren Schichten erscheinen, wobei die Anzahl der Vektoren mit aufsteigenden Schichten abnimmt. Obere Schichten ermöglichen Bewegungen über große Entfernungen, während untere Schichten eine detaillierte Suche in der Nähe vielversprechender Kandidaten erlauben.
Eine typische Suche beginnt an einem Einstiegspunkt in der höchsten Schicht. Bei jedem Schritt untersucht der Algorithmus benachbarte Knoten und bewegt sich zu einem, der näher an der Abfrage liegt. Wenn in dieser Schicht kein näherer Nachbar existiert, steigt er zur nächsten Schicht ab. In der untersten Schicht untersucht er eine breitere Kandidatenmenge und gibt die nächsten gefundenen Kandidaten zurück. Diese gierige Navigation wählt wiederholt lokal bessere Knoten, um sich dem Abfragepunkt zu nähern.
Konstruktion und Parameter
Der HNSW-Graph wird inkrementell aufgebaut. Beim Einfügen eines neuen Vektors weist der Algorithmus ihm eine maximale Schicht zu, sucht nach nahegelegenen vorhandenen Knoten und verbindet den neuen Knoten mit ausgewählten Nachbarn in jeder Schicht, in der er erscheint. Implementierungen legen Parameter offen, die Kompromisse zwischen Geschwindigkeit, Genauigkeit, Speichernutzung und Konstruktionszeit steuern. Höhere Graphverbindungen verbessern den Recall, erfordern jedoch mehr Speicher. Größere Suchkandidatenlisten verbessern die Genauigkeit, verlangsamen jedoch Abfragen. Größere Konstruktionskandidatenlisten verbessern die Graphqualität, verlangsamen jedoch den Indexaufbau.
Da HNSW approximativ ist, können Ergebnisse von exakten Suchen abweichen. Die praktische Leistung hängt von Datensatzeigenschaften, Distanzmaß, Implementierungsqualität und Parametereinstellungen ab. Benchmark-Studien haben gezeigt, dass HNSW-basierte Bibliotheken starke Leistungen unter approximativen Methoden für nächste Nachbarn erbringen, obwohl die Leistung im schlechtesten Fall von üblichen Benchmark-Ergebnissen abweichen kann.
Verwendung in Vektorsuchsystemen
HNSWLib wird als Index in Systemen verwendet, die hochdimensionale Vektoren speichern und durchsuchen, einschließlich Vektordatenbanken, Suchmaschinen und Datenbankerweiterungen. Typische Anwendungen umfassen semantische Suche, Empfehlungssysteme, Bildähnlichkeitssuche und retrieval-augmented generation. Die Bibliothek wird mit den ursprünglichen HNSW-Autoren in Verbindung gebracht und ist in Produktionsumgebungen weit verbreitet.
Mehrere Softwareprojekte implementieren oder unterstützen HNSW. Zu den Bibliotheken gehören HNSWLib und FAISS. Datenbank- und Suchsysteme, die HNSW-Unterstützung dokumentieren, umfassen Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant und Redis. Diese Systeme nutzen HNSW für schnelle approximative Suchen in Anwendungen, die von Large-Language-Model-Retrieval bis zu Generative-KI-Pipelines reichen.
Siehe auch
- Approximative Suche nach nächsten Nachbarn
- Vektordatenbank
- Lokalitätsempfindliches Hashing
- Produktquantisierung