🚀 Testen Sie Zilliz Cloud, die vollständig verwaltete Milvus, kostenlos – erleben Sie 10x schnellere Leistung! Jetzt testen>>

Verwaltetes Milvus

Home BlogsErste Schritte mit HNSWlib

Erste Schritte mit HNSWlib

Engineering

November 25, 2024

Haziqa Sajid

Diesemantische Suche ermöglicht es Maschinen, Sprache zu verstehen und bessere Suchergebnisse zu erzielen, was für die KI und die Datenanalyse unerlässlich ist. Sobald die Sprache als Einbettungen dargestellt ist, kann die Suche mit exakten oder approximativen Methoden durchgeführt werden. Die ungefähre Suche nach dem nächsten Nachbarn(Approximate Nearest Neighbor, ANN) ist eine Methode, mit der schnell die Punkte in einem Datensatz gefunden werden können, die einem bestimmten Abfragepunkt am nächsten liegen, im Gegensatz zur exakten Suche nach dem nächsten Nachbarn, die bei hochdimensionalen Daten sehr rechenintensiv sein kann. ANN ermöglicht einen schnelleren Abruf, indem es Ergebnisse liefert, die den nächsten Nachbarn annähernd entsprechen.

Einer der Algorithmen für die Approximate Nearest Neighbor (ANN)-Suche ist HNSW (Hierarchical Navigable Small Worlds), der unter HNSWlib implementiert ist und auf den wir uns heute konzentrieren werden. In diesem Blog werden wir:

Den HNSW-Algorithmus verstehen.
HNSWlib und seine Hauptmerkmale kennenlernen.
Einrichten von HNSWlib, einschließlich Indexerstellung und Suchimplementierung.
Vergleich mit Milvus.

Verstehen von HNSW

Hierarchical Navigable Small Worlds (HNSW) ist eine graphenbasierte Datenstruktur, die eine effiziente Ähnlichkeitssuche, insbesondere in hochdimensionalen Räumen, ermöglicht, indem sie einen mehrschichtigen Graphen aus "Small World"-Netzwerken aufbaut. Die 2016 eingeführte HNSW löst die Skalierbarkeitsprobleme, die mit herkömmlichen Suchmethoden wie Brute-Force- und baumbasierten Suchen verbunden sind. Es ist ideal für Anwendungen mit großen Datensätzen, wie Empfehlungssysteme, Bilderkennung und Retrieval-Augmented Generation (RAG).

Warum HNSW wichtig ist

HNSW verbessert die Leistung der Nearest-Neighbor-Suche in hochdimensionalen Räumen erheblich. Durch die Kombination der hierarchischen Struktur mit der Navigierbarkeit in kleinen Welten wird die rechnerische Ineffizienz älterer Methoden vermieden, so dass selbst bei großen, komplexen Datensätzen gute Ergebnisse erzielt werden können. Um dies besser zu verstehen, wollen wir uns nun ansehen, wie es funktioniert.

Wie HNSW funktioniert

Hierarchische Schichten: HNSW organisiert die Daten in einer Hierarchie von Ebenen, wobei jede Ebene Knoten enthält, die durch Kanten verbunden sind. Die obersten Ebenen sind spärlicher und ermöglichen ein weites "Überspringen" des Graphen, ähnlich wie das Herauszoomen aus einer Karte, um nur die wichtigsten Autobahnen zwischen Städten zu sehen. Die unteren Schichten werden immer dichter und bieten feinere Details und mehr Verbindungen zwischen näheren Nachbarn.
Konzept der navigierbaren kleinen Welten: Jede Ebene in HNSW baut auf dem Konzept eines "Small World"-Netzes auf, in dem die Knoten (Datenpunkte) nur wenige "Hops" voneinander entfernt sind. Der Suchalgorithmus beginnt auf der obersten, spärlichsten Ebene und arbeitet sich nach unten vor, wobei er sich zu immer dichteren Ebenen bewegt, um die Suche zu verfeinern. Auf diese Weise wird das Suchgebiet schrittweise eingegrenzt, indem man sich von einer globalen Ansicht bis hinunter zu Details auf Nachbarschaftsebene bewegt.

Abb. 1: Ein Beispiel für einen navigierbaren Small World Graph

Listenähnliche Struktur überspringen: Der hierarchische Aspekt von HNSW ähnelt einer Sprungliste, einer probabilistischen Datenstruktur, bei der höhere Ebenen weniger Knoten haben, was eine schnellere Anfangssuche ermöglicht.

Abb. 2: Ein Beispiel für eine Sprunglistenstruktur

Für die Suche nach 96 in der gegebenen Sprungliste beginnen wir auf der obersten Ebene ganz links beim Kopfknoten. Wenn wir uns nach rechts bewegen, stoßen wir auf 31, also weniger als 96, also fahren wir mit dem nächsten Knoten fort. Nun müssen wir eine Ebene tiefer gehen, wo wir wieder auf 31 stoßen; da es immer noch weniger als 96 ist, gehen wir eine weitere Ebene hinunter. Nachdem wir erneut 31 gefunden haben, gehen wir nach rechts und erreichen 96, unseren Zielwert. Auf diese Weise finden wir 96, ohne auf die untersten Ebenen der Sprungliste hinabsteigen zu müssen.

Such-Effizienz: Der HNSW-Algorithmus beginnt mit einem Einstiegsknoten auf der höchsten Ebene und rückt mit jedem Schritt zu näheren Nachbarn vor. Er steigt durch die Ebenen hinab, wobei er jede Ebene für eine grob- bis feinkörnige Erkundung nutzt, bis er die unterste Ebene erreicht, in der die ähnlichsten Knoten wahrscheinlich gefunden werden. Diese schichtweise Navigation reduziert die Anzahl der zu untersuchenden Knoten und Kanten und macht die Suche schnell und genau.
Einfügung und Pflege: Beim Hinzufügen eines neuen Knotens bestimmt der Algorithmus seine Eintrittsebene auf der Grundlage der Wahrscheinlichkeit und verbindet ihn mit nahegelegenen Knoten unter Verwendung einer Heuristik zur Auswahl von Nachbarn. Die Heuristik zielt darauf ab, die Konnektivität zu optimieren und Links zu erstellen, die die Navigierbarkeit verbessern und gleichzeitig die Graphendichte ausgleichen. Durch diesen Ansatz bleibt die Struktur robust und anpassungsfähig an neue Datenpunkte.

Obwohl wir ein grundlegendes Verständnis des HNSW-Algorithmus haben, kann die Implementierung von Grund auf überwältigend sein. Glücklicherweise hat die Community Bibliotheken wie HNSWlib entwickelt, um die Verwendung zu vereinfachen und den Zugang zu erleichtern, ohne sich den Kopf zu zerbrechen. Werfen wir also einen genaueren Blick auf HNSWlib.

Überblick über HNSWlib

HNSWlib, eine weit verbreitete Bibliothek zur Implementierung von HNSW, ist äußerst effizient und skalierbar und erbringt selbst bei Millionen von Punkten gute Leistungen. Sie erreicht eine sublineare Zeitkomplexität, indem sie schnelle Sprünge zwischen Graphenschichten ermöglicht und die Suche nach dichten, hochdimensionalen Daten optimiert. Hier sind die wichtigsten Merkmale von HNSWlib:

Graph-basierte Struktur: Ein mehrschichtiger Graph repräsentiert Datenpunkte und ermöglicht eine schnelle Suche nach den nächsten Nachbarn.
Hochdimensionale Effizienz: Optimiert für hochdimensionale Daten, ermöglicht schnelle und genaue Näherungssuchen.
Sublineare Suchzeit: Erreicht sublineare Komplexität durch das Überspringen von Schichten, was die Geschwindigkeit deutlich erhöht.
Dynamische Aktualisierungen: Unterstützt das Einfügen und Löschen von Knoten in Echtzeit, ohne dass ein kompletter Neuaufbau des Graphen erforderlich ist.
Speichereffizienz: Effiziente Speichernutzung, geeignet für große Datensätze.
Skalierbarkeit: Gute Skalierbarkeit für Millionen von Datenpunkten, ideal für mittelgroße Anwendungen wie Empfehlungssysteme.

Hinweis: HNSWlib eignet sich hervorragend für die Erstellung einfacher Prototypen für Vektorsuchanwendungen. Aufgrund der eingeschränkten Skalierbarkeit gibt es jedoch möglicherweise bessere Möglichkeiten, wie z. B. speziell entwickelte Vektordatenbanken für komplexere Szenarien mit Hunderten von Millionen oder sogar Milliarden von Datenpunkten. Lassen Sie uns das in Aktion sehen.

Erste Schritte mit HNSWlib: Eine Schritt-für-Schritt-Anleitung

In diesem Abschnitt wird die Verwendung von HNSWlib als Vektorsuchbibliothek demonstriert, indem ein HNSW-Index erstellt, Daten eingefügt und Suchen durchgeführt werden. Beginnen wir mit der Installation:

Einrichtung und Importe

Um mit HNSWlib in Python zu beginnen, installieren Sie es zunächst mit pip:

pip install hnswlib

Dann importieren Sie die erforderlichen Bibliotheken:

import hnswlib 
import numpy as np

Daten vorbereiten

In diesem Beispiel werden wir NumPyverwenden, um einen Zufallsdatensatz mit 10.000 Elementen zu erzeugen, jedes mit einer Dimension von 256.

dim = 256  # Dimensionality of your vectors
num_elements = 10000  # Number of elements to insert

Lassen Sie uns die Daten erstellen:

data = np.random.rand(num_elements, dim).astype(np.float32)  # Example data

Da unsere Daten nun bereit sind, können wir einen Index erstellen.

Erstellen eines Indexes

Um einen Index zu erstellen, müssen wir die Dimensionalität der Vektoren und den Raumtyp festlegen. Lassen Sie uns einen Index erstellen:

p = hnswlib.Index(space='l2', dim=dim)

space='l2': Dieser Parameter definiert die für die Ähnlichkeit verwendete Distanzmetrik. Wenn Sie ihn auf 'l2' setzen, wird der euklidische Abstand (L2-Norm) verwendet. Wenn Sie ihn stattdessen auf 'ip' setzen, wird das innere Produkt verwendet, was für Aufgaben wie Kosinusähnlichkeit hilfreich ist.

dim=dim: Dieser Parameter gibt die Dimensionalität der Datenpunkte an, mit denen Sie arbeiten werden. Er muss mit der Dimension der Daten übereinstimmen, die Sie dem Index hinzufügen möchten.

So initialisieren Sie einen Index:

p.init_index(max_elements=num_elements, ef_construction=200, M=16)

max_elements=num_elements: Hier wird die maximale Anzahl der Elemente festgelegt, die dem Index hinzugefügt werden können. Num_elements ist die maximale Kapazität, also setzen wir diese auf 10.000, da wir mit 10.000 Datenpunkten arbeiten.

ef_construction=200: Dieser Parameter steuert den Kompromiss zwischen Genauigkeit und Konstruktionsgeschwindigkeit bei der Indexerstellung. Ein höherer Wert verbessert die Wiederauffindbarkeit (Genauigkeit), erhöht aber den Speicherverbrauch und die Erstellungszeit. Übliche Werte reichen von 100 bis 200.

M=16: Dieser Parameter bestimmt die Anzahl der bidirektionalen Links, die für jeden Datenpunkt erstellt werden, und beeinflusst die Genauigkeit und die Suchgeschwindigkeit. Typische Werte liegen zwischen 12 und 48; 16 ist oft ein gutes Gleichgewicht für moderate Genauigkeit und Geschwindigkeit.

p.set_ef(50)  # This parameter controls the speed/accuracy trade-off

ef: Der Parameter ef, kurz für "Explorationsfaktor", bestimmt, wie viele Nachbarn bei einer Suche untersucht werden. Ein höherer ef Wert führt dazu, dass mehr Nachbarn untersucht werden, was im Allgemeinen die Genauigkeit (Recall) der Suche erhöht, sie aber auch langsamer macht. Umgekehrt kann ein niedriger ef Wert die Suche beschleunigen, aber auch die Genauigkeit verringern.

In diesem Fall bedeutet die Einstellung von ef auf 50, dass der Suchalgorithmus bei der Suche nach den ähnlichsten Datenpunkten bis zu 50 Nachbarn auswertet.

Hinweis: ef_construction legt den Aufwand für die Nachbarschaftssuche während der Indexerstellung fest, was die Genauigkeit erhöht, aber den Aufbau verlangsamt. ef steuert den Suchaufwand während der Abfrage, wobei Geschwindigkeit und Abruf für jede Abfrage dynamisch ausgeglichen werden.

Durchführen von Suchvorgängen

Um eine Suche nach nächsten Nachbarn mit HNSWlib durchzuführen, erstellen wir zunächst einen zufälligen Abfragevektor. In diesem Beispiel entspricht die Dimensionalität des Vektors den indizierten Daten.

query_vector = np.random.rand(dim).astype(np.float32)  # Example query

labels, distances = p.knn_query(query_vector, k=5)  # k is the number of nearest neighbors

query_vector: Diese Zeile erzeugt einen Zufallsvektor mit der gleichen Dimensionalität wie die indizierten Daten, um die Kompatibilität für die Nearest-Neighbour-Suche zu gewährleisten.
knn_query: Die Methode sucht nach den k nächsten Nachbarn von query_vector innerhalb des Index p. Sie gibt zwei Arrays zurück: labels, die die Indizes der nächsten Nachbarn enthalten, und distances, die die Entfernungen vom Abfragevektor zu jedem dieser Nachbarn angeben. Hier gibt k=5 an, dass wir die fünf nächsten Nachbarn finden wollen.

Hier sind die Ergebnisse nach dem Ausdrucken der Bezeichnungen und Abstände:

print("Nearest neighbors' labels:", labels)
print("Distances:", distances)

> Nearest neighbors' labels: [[4498 1751 5647 4483 2471]]
> Distances: [[33.718    35.484592 35.627766 35.828312 35.91495 ]]

Dies ist eine einfache Anleitung, um mit der HNSWlib loszulegen.

Wie bereits erwähnt, ist HNSWlib eine großartige Vektorsuchmaschine für das Prototyping oder das Experimentieren mit mittelgroßen Datensätzen. Wenn Sie höhere Anforderungen an die Skalierbarkeit haben oder andere Funktionen auf Unternehmensebene benötigen, sollten Sie sich für eine speziell entwickelte Vektordatenbank wie die Open-Source-Datenbank Milvus oder den vollständig verwalteten Dienst auf Zilliz Cloud entscheiden. Im folgenden Abschnitt werden wir HNSWlib mit Milvus vergleichen.

HNSWlib vs. zweckbestimmte Vektordatenbanken wie Milvus

Eine Vektordatenbank speichert Daten als mathematische Repräsentationen und ermöglicht es Modellen des maschinellen Lernens, die Suche, Empfehlungen und Texterstellung zu unterstützen, indem sie Daten durch Ähnlichkeitsmetriken für ein kontextuelles Verständnis identifiziert.

Bibliotheken mit Vektorindizes wie HNSWlib verbessern dieVektorsuche und -abfrage, verfügen jedoch nicht über die Verwaltungsfunktionen einer vollständigen Datenbank. Andererseits sind Vektordatenbanken wie Milvus darauf ausgelegt, Vektoreinbettungen in großem Umfang zu verarbeiten, und bieten Vorteile bei der Datenverwaltung, Indizierung und Abfragefunktionen, die eigenständigen Bibliotheken in der Regel fehlen. Hier sind einige weitere Vorteile der Verwendung von Milvus:

Hochgeschwindigkeits-Vektorähnlichkeitssuche: Milvus bietet eine Suchleistung im Millisekundenbereich über Vektordatensätze im Milliardenbereich, ideal für Anwendungen wie Bildabfrage, Empfehlungssysteme, Verarbeitung natürlicher Sprache(NLP) und Retrieval Augmented Generation(RAG).
Skalierbarkeit und Hochverfügbarkeit: Milvus wurde zur Bewältigung großer Datenmengen entwickelt, ist horizontal skalierbar und umfasst Replikations- und Failover-Mechanismen zur Gewährleistung der Zuverlässigkeit.
Verteilte Architektur: Milvus verwendet eine verteilte, skalierbare Architektur, die Speicher und Datenverarbeitung auf mehrere Knoten verteilt, um Flexibilität und Robustheit zu gewährleisten.
Hybride Suche: Milvus unterstützt multimodale Suche, hybride Sparse- und Dense-Suche sowie hybride Dense- und Volltextsuche und bietet damit vielseitige und flexible Suchfunktionen.
Flexible Datenunterstützung: Milvus unterstützt verschiedene Datentypen - Vektoren, Skalare und strukturierte Daten - und ermöglicht so eine nahtlose Verwaltung und Analyse innerhalb eines einzigen Systems.
Aktive Gemeinschaft und Unterstützung: Eine florierende Community bietet regelmäßige Updates, Tutorials und Support, um sicherzustellen, dass Milvus stets an den Bedürfnissen der Benutzer und den Fortschritten in diesem Bereich ausgerichtet ist.
KI-Integration: Milvus ist in verschiedene gängige KI-Frameworks und -Technologien integriert, was es Entwicklern erleichtert, Anwendungen mit ihren vertrauten Technologie-Stacks zu erstellen.

Milvus bietet auch einen vollständig verwalteten Service in der Ziliz Cloud, der problemlos und 10x schneller als Milvus ist.

Vergleich: Milvus vs. HNSWlib

Merkmal	Milvus	HNSWlib
Skalierbarkeit	Einfache Handhabung von Milliarden von Vektoren	Geeignet für kleinere Datensätze aufgrund der RAM-Nutzung
Ideal für	Prototyping, Experimentieren und Anwendungen auf Unternehmensebene	Konzentriert sich auf Prototypen und leichte ANN-Aufgaben
Indizierung	Unterstützt 10+ Indizierungsalgorithmen, einschließlich HNSW, DiskANN, Quantisierung und Binär	Verwendet nur einen graphbasierten HNSW
Integration	Bietet APIs und Cloud-native Dienste	Dient als leichtgewichtige, eigenständige Bibliothek
Leistung	Optimiert für große Daten und verteilte Abfragen	Bietet hohe Geschwindigkeit, aber begrenzte Skalierbarkeit

Insgesamt ist Milvus im Allgemeinen für groß angelegte, produktionsreife Anwendungen mit komplexen Indizierungsanforderungen zu bevorzugen, während HNSWlib ideal für Prototypen und einfachere Anwendungsfälle ist.

Schlussfolgerung

Die semantische Suche kann ressourcenintensiv sein, so dass eine interne Datenstrukturierung, wie sie von HNSW vorgenommen wird, für einen schnelleren Datenabruf unerlässlich ist. Bibliotheken wie HNSWlib kümmern sich um die Implementierung, so dass die Entwickler die Rezepte für die Prototypisierung von Vektorfunktionen zur Hand haben. Mit nur wenigen Codezeilen können wir unseren eigenen Index aufbauen und Suchvorgänge durchführen.

HNSWlib ist ein guter Anfang. Wenn Sie jedoch komplexe und produktionsreife KI-Anwendungen erstellen möchten, sind speziell entwickelte Vektordatenbanken die beste Option. Milvus zum Beispiel ist eine Open-Source-Vektordatenbank mit vielen unternehmenstauglichen Funktionen wie Hochgeschwindigkeits-Vektorsuche, Skalierbarkeit, Verfügbarkeit und Flexibilität in Bezug auf Datentypen und Programmiersprache.