DiskANN, eine festplattenbasierte ANNS-Lösung mit hohem Recall und hoher QPS auf einem milliardenschweren Datensatz
Chengming Li, Forschungs- und Entwicklungsingenieur bei Zilliz, hat an der SouthEast University einen Master-Abschluss in Informatik erworben. Sein derzeitiger Schwerpunkt liegt auf ANNS-Problemen bei hochdimensionalen Daten, einschließlich graphbasierter und quantisierungsbasierter Lösungen.
"DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node" ist ein Paper, das 2019 auf NeurIPS veröffentlicht wurde. Das Paper stellt eine hochmoderne Methode zur Indexerstellung und -suche auf dem Milliarden-Datensatz vor, bei der eine einzige Maschine mit nur 64 GB RAM und einer ausreichend großen SSD zum Einsatz kommt. Darüber hinaus erfüllt sie die drei Anforderungen von ANNS (Approximate Nearest Neighbor Search) auf dem großen Datensatz: hoher Recall, niedrige Latenz und hohe Dichte (Anzahl der Knoten auf einer einzigen Maschine). Diese Methode erstellt einen graphenbasierten Index auf einem milliardenschweren Datensatz SIFT-1B unter Verwendung einer einzigen Maschine mit 64 GB RAM und einer 16-Kern-CPU und erreicht 5000 QPS (Abfragen pro Sekunde) bei über 95 % Recall@1 und einer durchschnittlichen Latenzzeit von weniger als 3 ms.
Autoren
Suhas Jayaram Subramanya: Ehemaliger Mitarbeiter des Microsoft India Research Institute, Doktorand an der CMU. Seine Hauptforschungsinteressen sind High-Performance-Computing und Algorithmen für maschinelles Lernen bei großen Datenmengen.
Devvrit: Forschungsassistent an der Universität von Texas in Austin. Seine Forschungsinteressen sind theoretische Informatik, maschinelles Lernen und Deep Learning.
Rohan Kadekodi: Promotionsstudent an der Universität von Texas. Seine Forschungsrichtung ist System und Speicherung, hauptsächlich einschließlich persistenter Speicherung, Dateisystem und kV-Speicherung.
Ravishankar Krishaswamy: Hauptforscher am indischen Forschungsinstitut von Microsoft. Doktor der CMU. Die Forschungsrichtung ist der Annäherungsalgorithmus auf der Grundlage von Graph und Clustering.
Harsha Vardhan Simhadri: Hauptforscher des indischen Forschungsinstituts von Microsoft. Doktor der CMU. In der Vergangenheit hat er parallele Algorithmen und Laufzeitsysteme untersucht. Jetzt besteht seine Hauptarbeit darin, neue Algorithmen zu entwickeln und Programmiermodelle zu schreiben.
Beweggründe
Die meisten der gängigen ANNS-Algorithmen gehen Kompromisse zwischen Indexaufbauleistung, Suchleistung und Rückruf ein. Graphenbasierte Algorithmen wie HNSW und NSG sind in Bezug auf die Suchleistung und die Wiederauffindbarkeit derzeit die modernsten Methoden. Da die speicherresidente graphenbasierte Indizierungsmethode zu viel Speicherplatz beansprucht, ist es relativ schwierig, einen großen Datensatz auf einem einzigen Rechner mit begrenzten Speicherressourcen zu indizieren und zu durchsuchen.
Viele Anwendungen erfordern eine schnelle Reaktion des auf der euklidischen Distanz basierenden ANNS auf dem Milliarden-Datensatz. Im Folgenden werden zwei Hauptlösungen vorgestellt:
- Invertierter Index + Quantisierung: Der Datensatz wird in M Partitionen geclustert und mithilfe von Quantisierungsverfahren wie PQ (Product Quantization) komprimiert. Diese Lösung führt zu einem niedrigen Recall, da die Datenkomprimierung einen Präzisionsverlust zur Folge hat. Eine Erhöhung von topk trägt zur Verbesserung der Wiederauffindbarkeit bei, während die QPS entsprechend sinken würde.
- Aufteilen und indexieren: Der Datensatz wird in mehrere disjunkte Shards aufgeteilt und für jeden Shard ein speicherinterner Index erstellt. Bei Abfrageanfragen wird die Suche in den Indizes der einzelnen Shards durchgeführt und die Ergebnisse werden nach der Zusammenführung zurückgegeben. Diese Lösung führt zu einer übermäßigen Vergrößerung des Datenbestands, so dass aufgrund der begrenzten Speicherressourcen auf einem einzelnen Rechner mehr Maschinen benötigt werden, was zu einer niedrigen QPS führt.
Beide oben genannten Lösungen sind durch die Speicherbeschränkung eines einzelnen Rechners begrenzt. In diesem Papier wird der Entwurf eines SSD-residenten Indizierungsmechanismus vorgeschlagen, um dieses Problem zu lösen. Die Herausforderung der SSD-residenten Indizierung besteht darin, die Anzahl der zufälligen Festplattenzugriffe und die Anzahl der Anfragen für Festplattenzugriffe zu reduzieren.
Beiträge
In diesem Papier wird ein SSD-residentes ANNS-Schema namens DiskANN vorgestellt, das die Suche in großen Datensätzen effektiv unterstützen kann. Dieses Schema basiert auf einem graphbasierten Algorithmus, der in diesem Beitrag vorgestellt wird: Vamana. Die Beiträge dieses Papiers umfassen:
- DiskANN kann einen milliardenschweren Datensatz mit mehr als 100 Dimensionen auf einem einzigen Rechner mit 64 GB RAM indizieren und durchsuchen und bietet dabei eine Wiedererkennungsrate von über 95 %@1 bei Latenzzeiten von unter 5 Millisekunden.
- Ein neuer graphenbasierter Algorithmus namens Vamana mit einem kleineren Suchradius als bei NSG und HNSW wurde vorgeschlagen, um die Anzahl der Festplattenzugriffe zu minimieren.
- Vamana kann im Speicher arbeiten und seine Leistung ist nicht langsamer als die von NSG und HNSW.
- Kleinere Vamana-Indizes, die auf überlappenden Partitionen des großen Datensatzes aufgebaut sind, können zu einem Graphen zusammengeführt werden, ohne dass die Konnektivität verloren geht.
- Vamana kann mit Quantisierungsverfahren wie PQ kombiniert werden. Die Graphenstruktur und die Originaldaten werden auf der Festplatte gespeichert, während die komprimierten Daten im Speicher gehalten werden.
Vamana
Dieser Algorithmus ähnelt der Idee von NSG[2][4] (für diejenigen, die NSG nicht verstehen, sei auf Referenz [2] verwiesen, und wenn Sie keine Papiere lesen wollen, können Sie auf Referenz [4] verweisen). Ihr Hauptunterschied liegt in der Trimmstrategie. Um genau zu sein, wurde der Trimmstrategie des NSG ein Schalter alpha hinzugefügt. Der Grundgedanke der NSG-Trimmstrategie ist, dass die Auswahl der Nachbarn des Zielpunktes so vielfältig wie möglich ist. Wenn der neue Nachbar näher an einem Nachbarn des Zielpunktes liegt als der Zielpunkt, brauchen wir diesen Punkt nicht in die Menge der Nachbarpunkte aufzunehmen. Mit anderen Worten, für jeden Nachbarn des Zielpunkts darf es keine weiteren Nachbarpunkte innerhalb des Umkreises dist (Zielpunkt, Nachbarpunkt) geben. Mit dieser relativ radikalen Trimmstrategie wird der Außengrad des Graphen wirksam kontrolliert. Sie reduziert den Speicherbedarf des Index, verbessert die Suchgeschwindigkeit, verringert aber auch die Suchgenauigkeit. Die Trimmstrategie von Vamana besteht darin, das Ausmaß des Trimmens durch den Parameter alpha frei zu steuern. Das Arbeitsprinzip besteht darin, die Dist (Nachbarpunkt, Kandidatenpunkt) in der Trimmbedingung mit einem Parameter alpha (nicht kleiner als 1) zu multiplizieren. Nur wenn dist (Zielpunkt, ein bestimmter Kandidatenpunkt) größer ist als der vergrößerte Referenzabstand, wird die Trimmstrategie angewandt und die Toleranz des gegenseitigen Ausschlusses zwischen den Nachbarn des Zielpunktes erhöht.
Der Indizierungsprozess von Vamana ist relativ einfach:
- Initialisieren eines Zufallsgraphen;
- Berechnen des Startpunktes, der dem Navigationspunkt des NSG ähnelt. Zunächst wird der globale Schwerpunkt ermittelt und dann der Punkt, der dem globalen Schwerpunkt am nächsten liegt, als Navigationspunkt festgelegt. Der Unterschied zwischen Vamana und NSG besteht darin, dass die Eingabe von NSG bereits ein Nearest Neighbour Graph ist, so dass der Benutzer einfach eine ungefähre Nearest Neighbour Suche nach dem Schwerpunktpunkt direkt auf dem anfänglichen Nachbargraphen durchführen kann. Vamana hingegen initialisiert einen zufälligen Graphen der nächsten Nachbarn, so dass die Benutzer keine ungefähre Suche direkt auf dem zufälligen Graphen durchführen können. Sie müssen einen globalen Vergleich durchführen, um einen Navigationspunkt als Ausgangspunkt für nachfolgende Iterationen zu erhalten. Der Zweck dieses Punktes ist es, den durchschnittlichen Suchradius zu minimieren;
- Approximate Nearest Neighbor Search (Näherungsweise Suche nach dem nächsten Nachbarn) für jeden Punkt auf der Grundlage des initialisierten Zufallsgraphen und des in Schritt 2 bestimmten Startpunkts der Suche, wobei alle Punkte auf dem Suchpfad als Kandidaten-Nachbarn festgelegt werden und die Kantenbeschneidungsstrategie mit alpha = 1 ausgeführt wird. Ähnlich wie bei NSG wird die Auswahl der Punkte auf dem Suchpfad, der vom Navigationspunkt ausgeht, als Nachbarschaftskandidaten einige lange Kanten vergrößern und den Suchradius effektiv reduzieren.
- Stellen Sie alpha > 1 ein (im Papier wird 1,2 empfohlen) und wiederholen Sie Schritt 3. Während Schritt 3 auf einem zufälligen Graphen der nächsten Nachbarn basiert, ist der Graph nach der ersten Iteration von geringer Qualität. Daher ist eine weitere Iteration erforderlich, um die Qualität des Graphen zu verbessern, was für die Wiederfindungsrate sehr wichtig ist.
In diesem Beitrag werden die drei Graphenindizes Vamana, NSG und HNSW miteinander verglichen. In Bezug auf die Indizierungs- und Abfrageleistung liegen Vamana und NSG relativ dicht beieinander und übertreffen beide den HNSW leicht. Die Daten finden Sie im Abschnitt Experiment weiter unten.
2.png
Zur Veranschaulichung des Aufbauprozesses des Vamana-Indexes enthält das Papier ein Diagramm, in dem 200 zweidimensionale Punkte verwendet werden, um zwei Iterationsrunden zu simulieren. In der ersten Zeile wird Alpha = 1 verwendet, um die Kanten zu beschneiden. Es ist zu erkennen, dass die Beschneidungsstrategie relativ radikal ist und eine große Anzahl von Kanten beschnitten wird. Nachdem der Wert alpha erhöht und die Trimmbedingungen gelockert wurden, werden offensichtlich viele Kanten wieder hinzugefügt. Im endgültigen Graphen werden ziemlich viele lange Kanten hinzugefügt. Dadurch kann der Suchradius effektiv reduziert werden.
DiskANN
Ein Personalcomputer mit nur 64 GB Speicherplatz würde nicht einmal eine Milliarde Rohdaten aufnehmen können, geschweige denn den darauf aufgebauten Index. Hier gibt es zwei Herausforderungen: 1. Wie kann ein so großer Datensatz mit begrenzten Speicherressourcen indiziert werden? 2. Wie kann die Entfernung bei der Suche berechnet werden, wenn die Originaldaten nicht in den Speicher geladen werden können?
In dem Papier werden die folgenden Lösungen vorgeschlagen:
- Für die erste Herausforderung: Zunächst werden die Daten mit Hilfe von k-means in k Cluster aufgeteilt, und dann wird jeder Punkt den nächstgelegenen i Clustern zugeordnet. Im Allgemeinen sind 2 für die Anzahl i ausreichend. Erstellen Sie einen speicherbasierten Vamana-Index für jeden Cluster, und fügen Sie schließlich k Vamana-Indizes zu einem zusammen.
- Für die zweite Herausforderung: Erstellen Sie einen Index auf den ursprünglichen Vektoren und fragen Sie die komprimierten Vektoren ab. Die Erstellung von Indizes auf dem ursprünglichen Vektor gewährleistet die Qualität des Graphen, während der komprimierte Vektor für die grobkörnige Suche in den Speicher geladen werden kann. Obwohl die Suche mit den komprimierten Vektoren zu einem Verlust an Genauigkeit führen kann, wird die allgemeine Richtung korrekt sein, solange die Qualität des Graphen hoch genug ist. Das endgültige Abstandsresultat wird anhand des ursprünglichen Vektors berechnet.
Der Indexaufbau von DiskANN ähnelt dem der allgemeinen Graph-Indizes. Der Nachbarsatz jedes Punktes und die ursprünglichen Vektordaten werden zusammen gespeichert. Dadurch wird die Lokalität der Daten besser ausgenutzt.
Wie bereits erwähnt, müssen bei der Speicherung der Indexdaten auf der SSD die Anzahl der Festplattenzugriffe sowie die Lese- und Schreibanforderungen so weit wie möglich reduziert werden, um eine geringe Suchverzögerung zu gewährleisten. Daher schlägt DiskANN zwei Optimierungsstrategien vor:
- Cache-Hotspot: alle Punkte innerhalb von C-Sprüngen vom Startpunkt im Speicher cachen. Der Wert von C wird am besten auf 3 bis 4 gesetzt.
- Balkensuche: Einfach ausgedrückt, werden die Nachbarinformationen vorgeladen. Bei der Suche nach dem Punkt p muss der Nachbarpunkt von p von der Festplatte geladen werden, wenn er sich nicht im Speicher befindet. Da eine kleine Menge von SSD-Zufallszugriffsoperationen etwa die gleiche Zeit wie eine SSD-Einzelsektor-Zugriffsoperation benötigt, können die Nachbarinformationen von W nicht zugegriffenen Punkten auf einmal geladen werden. W kann weder zu groß noch zu klein gewählt werden. Ein großes W wird Rechenressourcen und SSD-Bandbreite verschwenden, während ein kleines W die Suchverzögerung erhöht.
Experiment
Das Experiment besteht aus drei Gruppen:
Vergleich zwischen speicherbasierten Indizes: Vamana VS. NSG VS. HNSW
Datensätze: SIFT1M (128 Dimensionen), GIST1M (960 Dimensionen), DEEP1M (96 Dimensionen) und ein 1M-Datensatz, der zufällig aus DEEP1B entnommen wurde.
Index-Parameter (alle Datensätze verwenden den gleichen Satz von Parametern):
HNSW:M = 128, efc = 512.
Vamana: R = 70, L = 75, alpha = 1,2.
NSG: R = 60, L = 70, C= 500.
Die Suchparameter werden in dem Papier nicht angegeben, was mit den Indizierungsparametern übereinstimmen könnte. Bei der Auswahl der Parameter basieren die im Artikel genannten Parameter von NSG auf den im GitHub-Repository von NSG aufgeführten Parametern, um die Gruppe mit der besseren Leistung auszuwählen. Vamana und NSG liegen relativ nah beieinander, so dass auch die Parameter ähnlich gesetzt sind. Der Grund für die Auswahl der HNSW-Parameter wird jedoch nicht genannt. Wir glauben, dass der Parameter M von HNSW relativ groß eingestellt ist. Es könnte zu einem weniger überzeugenden Vergleich zwischen graphenbasierten Indizes führen, wenn ihre out-degrees nicht auf das gleiche Niveau gesetzt werden.
Unter den oben genannten Indizierungsparametern beträgt die Indizierungszeit von Vamana, HNSW und NSG jeweils 129s, 219s und 480s. Die NSG-Indizierungszeit beinhaltet die Zeit für die Erstellung des anfänglichen Nachbargraphen mit EFANN [3].
Recall-QPS-Kurve:
3.png
Aus Abbildung 3 ist ersichtlich, dass Vamana bei den drei Datensätzen eine hervorragende Leistung erbringt, ähnlich wie NSG und etwas besser als HNSW.
Vergleich des Suchradius:
Aus Abbildung 2.c ist ersichtlich, dass Vamana im Vergleich zu NSG und HNSW den kürzesten durchschnittlichen Suchweg bei gleicher Recall-Rate aufweist.
Vergleich zwischen einem einmalig erstellten Index und einem großen zusammengeführten Index
Datensatz: SIFT1B
Die Parameter des einmalig aufgebauten Index: L = 50, R = 128, alpha = 1,2. Nach einer Laufzeit von 2 Tagen auf einem 1800G DDR3-Rechner beträgt der Spitzenspeicher etwa 1100 G und der durchschnittliche Out-degree 113,9.
Indizierungsverfahren auf der Grundlage der Zusammenführung:
- Trainieren von 40 Clustern auf dem Datensatz mit kmeans;
- Jeder Punkt wird auf die 2 nächstgelegenen Cluster verteilt;
- Erstellen eines Vamana-Index mit L = 50, R = 64 und Alpha = 1,2 für jeden Cluster;
- Zusammenführen der Indizes der einzelnen Cluster.
Dieser Index generierte einen 384 GB großen Index mit einem durchschnittlichen Out-of-degree von 92,1. Dieser Index wurde 5 Tage lang auf einem 64 GB DDR4-Rechner ausgeführt.
Die Vergleichsergebnisse sehen wie folgt aus (Abbildung 2a):
4.png
Zusammengefasst:
- Der einmalig erstellte Index ist deutlich besser als der auf Zusammenführung basierende Index;
- Der auf Merging basierende Index ist ebenfalls hervorragend;
- Das Merging-basierte Indexierungsschema ist auch auf den DEEP1B-Datensatz anwendbar (Abbildung 2b).
Plattenbasierter Index: DiskANN VS. FAISS VS. IVF-OADC+G+P
IVFOADC+G+P ist ein Algorithmus, der in Referenz [5] vorgeschlagen wurde.
In diesem Papier wird nur DiskANN mit IVFOADC+G+P verglichen, da in der Referenz [5] nachgewiesen wurde, dass IVFOADC+G+P besser ist als FAISS. Darüber hinaus erfordert FAISS GPU-Ressourcen, die nicht von allen Plattformen unterstützt werden.
IVF-OADC+G+P scheint eine Kombination aus HNSW und IVF-PQ zu sein. Es bestimmt Cluster mithilfe von HNSW und führt die Suche durch, indem es dem Zielcluster einige Beschneidungsstrategien hinzufügt.
Das Ergebnis ist in Abbildung 2a dargestellt. Die 16 und 32 in der Abbildung sind die Codebuchgröße. Der Datensatz ist SIFT1B, quantifiziert durch OPQ.
Details zur Code-Implementierung
Der Quellcode von DiskANN ist auf https://github.com/microsoft/DiskANN frei zugänglich.
Im Januar 2021 wurde der Quellcode der DiskANN-Lösung als Open Source zur Verfügung gestellt.
Im Folgenden werden hauptsächlich der Indizierungsprozess und der Suchprozess vorgestellt.
Indexerstellung
Es gibt 8 Parameter für die Indexerstellung:
data_type: Die Optionen umfassen float/int8/uint8.
data_file.bin: Die ursprüngliche Binärdatei der Daten. Die ersten beiden Ganzzahlen in der Datei stehen für die Gesamtzahl n des Datensatzvektors und die Vektordimension dim. Die letzten n dim sizeof(data_type) Bytes sind kontinuierliche Vektordaten.
index_prefix_pfad: Das Pfadpräfix der Ausgabedatei. Nachdem der Index aufgebaut ist, werden mehrere indexbezogene Dateien erzeugt. Dieser Parameter ist das gemeinsame Präfix des Verzeichnisses, in dem sie gespeichert sind.
R: Der maximale Out-Grad des globalen Indexes.
L: Der Parameter L des Vamana-Index, die obere Grenze der Kandidatenmenge.
B: Die Speicherschwelle bei Abfragen. Er steuert die Größe des PQ-Codebuchs in GB.
M: Die Speicherschwelle beim Aufbau eines Index. Er bestimmt die Größe des Fragments in GB.
T: Die Anzahl der Threads.
Indizierungsprozess (Eingangsfunktion: aux_utils.cpp::build_disk_index):
- Erzeugen verschiedener Ausgabedateinamen gemäß index_prefix_path.
- Parameter-Prüfung.
- Lesen der Metadaten von data_file.bin, um n und dim zu erhalten. Bestimmen der Codebuch-Unterraumnummer m von PQ entsprechend B und n.
- generate_pq_pivots: Nehmen Sie den Mittelpunkt der PQ-Trainingsmenge mit der Abtastrate von p = 1500000/n gleichmäßig ab, um PQ global zu trainieren.
- generate_pq_data_from_pivots: Erzeugt ein globales PQ-Codebuch und speichert den Mittelpunkt und das Codebuch separat.
- build_merged_vamana_index: Zerlegen des ursprünglichen Datensatzes, Erstellen von Vamana-Indizes in Segmenten und schließlich Zusammenführen der Indizes zu einem Index.
- partition_mit_ram_budget: Bestimmen Sie die Anzahl der Fragmente k entsprechend dem Parameter M. Ziehen Sie eine Stichprobe des Datensatzes mit kmeans, wobei Sie jeden Punkt auf zwei nächstgelegene Cluster aufteilen. Fragmentieren Sie den Datensatz, und jedes Fragment erzeugt zwei Dateien: eine Datendatei und eine ID-Datei. Die ID-Datei und die Datendatei entsprechen einander, und jede ID in der ID-Datei entspricht einem Vektor in der Datendatei. Die IDs werden durch die Nummerierung jedes Vektors der Originaldaten von 0 bis n-1 ermittelt. Die ID ist relativ wichtig und steht im Zusammenhang mit der Zusammenführung.
- Führen Sie eine globale, gleichmäßige Stichprobe der Trainingsmenge mit einer Abtastrate von 1500000 / n durch;
- Initialisiere num_parts = 3. Iteriere von 3:
- Führen Sie num_parts-means++ auf der Trainingsmenge in Schritt i durch;
- Verwenden Sie eine Abtastrate von 0,01, um eine einheitliche globale Abtastung der Testmenge durchzuführen, und unterteilen Sie die Testmenge in die 2 nächstgelegenen Cluster;
- Zählen Sie die Anzahl der Punkte in jedem Cluster und teilen Sie sie durch die Stichprobenrate, um die Anzahl der Punkte in jedem Cluster zu schätzen;
- Schätzen Sie den Speicherbedarf des größten Clusters in Schritt 3 entsprechend der Vamana-Indexgröße; wenn er den Parameter M nicht überschreitet, fahren Sie mit Schritt iii fort, andernfalls num_parts ++ kehren Sie zu Schritt 2 zurück;
- Aufteilung des Originaldatensatzes in num_parts-Gruppendateien, jede Dateigruppe enthält fragmentierte Datendateien und ID-Dateien, die den fragmentierten Daten entsprechen.
- Erstellen Sie Vamana-Indizes separat für alle Slices in Schritt a und speichern Sie sie auf der Festplatte;
- merge_shards: Zusammenführen von num_parts shard Vamana in einen globalen Index:
- Einlesen der ID-Datei von num_parts-Fragmenten in idmap. Diese idmap ist gleichbedeutend mit der Erstellung einer Vorwärtsabbildung von fragment->id;
- Erstellen Sie eine umgekehrte Zuordnung von id-> Fragmente gemäß idmap, und wissen Sie, in welchen zwei Fragmenten sich jeder Vektor befindet;
- Verwenden Sie einen Reader mit 1 GB Cache, um num_parts slice Vamana-Indizes zu öffnen, und verwenden Sie einen Writer mit 1 GB Cache, um die Ausgabedatei zu öffnen, bereit zum Zusammenführen;
- Platzieren Sie num_parts Navigationspunkte des Vamana-Indexes in die Mittelpunktsdatei, die bei der Suche verwendet wird;
- Beginn der Zusammenführung entsprechend der ID von klein bis groß, Lesen der Nachbarpunkte jedes ursprünglichen Vektors in jedem Fragment entsprechend der umgekehrten Zuordnung, Deduplizierung, Shuffle, Trunkierung und Schreiben in die Ausgabedatei. Da das Slicing ursprünglich global geordnet war und nun auch das Merging geordnet ist, stimmen die ID im endgültigen Flush-Index und die ID der Originaldaten eins-zu-eins überein.
- Löschen von temporären Dateien, einschließlich Fragmentdateien, Fragmentindizes und Fragment-ID-Dateien.
erstellen_disk_layout: Der in Schritt 6 erzeugte globale Index hat nur eine kompakte Adjazenztabelle. Dieser Schritt dient dazu, den Index auszurichten. Die Adjazenztabelle und die Originaldaten werden zusammen gespeichert. Bei der Suche müssen die Adjazenztabelle und der ursprüngliche Vektor zusammen geladen werden, um eine genaue Abstandsberechnung zu ermöglichen. Es gibt auch das Konzept der SECTORs, deren Standardgröße 4096 beträgt. Jeder SECTOR enthält nur 4096 / node_size Teile der Vektorinformationen. node_size = Größe des einzelnen Vektors + Größe der Adjazenztabelle des einzelnen Knotens.
Schließlich führen Sie eine globale einheitliche Stichprobe von 150000 / n durch, speichern diese und verwenden sie zum Aufwärmen bei der Suche.
Suche
Es gibt 10 Suchparameter:
- index_type: Zu den Optionen gehören Float/int8/uint8, ähnlich wie der erste Parameter data_type beim Aufbau eines Index.
- index_prefix_path: Siehe den Index-Parameter index_prefix_path.
- num_nodes_to_cache: Anzahl der Cache-Hotspots.
- num_threads: Anzahl der Such-Threads.
- beamwidth: Obere Grenze für die Anzahl der Preload-Punkte. Das System bestimmt, ob sie auf 0 gesetzt wird.
- query_file.bin: Abfragesatz-Datei.
- truthset.bin: Ergebnismengen-Datei, "null" bedeutet, dass die Ergebnismenge nicht bereitgestellt wird, das Programm berechnet sie selbst;
- K: topk;
- result_output_prefix: Pfad zum Speichern der Suchergebnisse;
- L*: Liste der Suchparameter. Es können mehrere Werte hinzugefügt werden. Für jedes L werden statistische Informationen bei der Suche mit verschiedenen L gegeben.
Suchprozess:
- Laden der zugehörigen Daten: Laden des Abfragesatzes, der PQ-Mittelpunktsdaten, der Codebuchdaten, des Suchstartpunkts und anderer Daten sowie Lesen der Indexmetadaten.
- Verwenden Sie den während der Indizierung abgetasteten Datensatz für die cached_beam_search, zählen Sie die Zugriffszeiten jedes Punktes und laden Sie die num_nodes_to_cache Punkte mit der höchsten Zugriffshäufigkeit in den Cache.
- Standardmäßig gibt es einen WARMUP-Vorgang. Wie in Schritt 2 wird dieser Beispieldatensatz auch für eine cached_beam_search verwendet.
- Je nach der Anzahl der angegebenen Parameter L wird jeder L mit cached_beam_search erneut mit dem Abfragesatz durchgeführt, und es werden Statistiken wie Recall-Rate und QPS ausgegeben. Der Prozess des Aufwärmens und der statistischen Hotspot-Daten wird nicht in die Abfragezeit eingerechnet.
Über cached_beam_search:
- Suche nach dem nächstgelegenen Kandidaten zum Abfragepunkt vom Kandidatenstartpunkt aus. Hier wird die PQ-Distanz verwendet, und der Startpunkt wird der Suchwarteschlange hinzugefügt.
- Suche starten:
- Von der Suchwarteschlange gibt es nicht mehr als beam_width + 2 unbesuchte Punkte. Wenn sich diese Punkte im Cache befinden, werden sie in die Cache-Treffer-Warteschlange aufgenommen. Wenn sie nicht getroffen wurden, fügen Sie sie der Miss-Warteschlange hinzu. Achten Sie darauf, dass die Größe der Miss-Warteschlange nicht größer ist als beam_width.
- Senden Sie asynchrone Plattenzugriffsanforderungen an Punkte in der Miss-Warteschlange.
- Für die Punkte, die vom Cache getroffen wurden, verwenden Sie die Originaldaten und die Abfragedaten, um die genaue Entfernung zu berechnen, fügen Sie sie der Ergebnis-Warteschlange hinzu und verwenden Sie dann PQ, um die Entfernung zu den Nachbarpunkten zu berechnen, die noch nicht besucht wurden, bevor Sie sie der Such-Warteschlange hinzufügen. Die Länge der Suchschlange ist durch Parameter begrenzt.
- Verarbeiten Sie die zwischengespeicherten Fehlpunkte in Schritt a, ähnlich wie in Schritt c.
- Wenn die Suchwarteschlange leer ist, endet die Suche, und die Ergebniswarteschlange topk wird zurückgegeben.
Zusammenfassen
Obwohl dies eine relativ lange Arbeit ist, ist sie insgesamt ausgezeichnet. Die Ideen des Papiers und des Codes sind klar: Aufteilung einer Reihe von sich überlappenden Bereichen durch k-means, dann Aufteilung der Bereiche, um einen Map-Index zu erstellen, und schließlich Zusammenführung der Indizes, was eine relativ neue Idee ist. Was den speicherbasierten Graphenindex Vamana betrifft, so handelt es sich im Wesentlichen um eine zufällig initialisierte Version von NSG, die die Granularität des Trimmens steuern kann. Bei Abfragen nutzt er den Cache und die Pipeline voll aus, deckt einen Teil der IO-Zeit ab und verbessert die QPS. Dem Papier zufolge dauert die Einarbeitungszeit jedoch bis zu 5 Tage, und die Benutzerfreundlichkeit ist relativ gering, selbst wenn die Maschinenbedingungen nicht außergewöhnlich sind. Optimierungen des Trainings sind in Zukunft definitiv notwendig. Aus Sicht des Codes ist die Qualität relativ hoch und kann direkt in der Produktionsumgebung verwendet werden.
Referenzen
- Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, Rohan Kadekodi. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS 2019.
- [Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graphs. PVLDB, 12(5):461 - 474, 2019. doi: 10.14778/3303753.3303754.] (http://www.vldb.org/pvldb/vol12/p461-fu.pdf)
- Cong Fu und Deng Cai. GitHub - ZJULearning/efanna: schnelle Bibliothek für ANN-Suche und KNN-Graphenkonstruktion.
- Suchmaschine für AI:高维数据检索工业级解决方案
Try Managed Milvus for Free
Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.
Get StartedLike the article? Spread the word