🚀 Essayez Zilliz Cloud, la version entièrement gérée de Milvus, gratuitement—découvrez des performances 10x plus rapides ! Essayez maintenant>>

Commencer

Home
Blog
DiskANN, une solution ANNS basée sur un disque avec un rappel élevé et un QPS élevé sur un ensemble de données à l'échelle du milliard

DiskANN, une solution ANNS basée sur un disque avec un rappel élevé et un QPS élevé sur un ensemble de données à l'échelle du milliard

Engineering

September 24, 2021

Zilliz

Chengming Li, ingénieur en recherche et développement chez Zilliz, est titulaire d'une maîtrise en informatique de l'université SouthEast. Il s'intéresse actuellement aux problèmes ANNS sur les données de haute dimension, y compris les solutions basées sur les graphes et la quantification.

"DiskANN : Fast Accurate Billion-point Nearest Neighbor Search on a Single Node" est un article publié sur NeurIPS en 2019. L'article présente une méthode de pointe pour effectuer la construction d'un index et la recherche sur le jeu de données à l'échelle du milliard en utilisant une seule machine avec seulement 64 Go de RAM et un SSD suffisamment grand. En outre, cette méthode répond aux trois exigences de la méthode ANNS (Approximate Nearest Neighbor Search) sur l'ensemble de données à grande échelle : rappel élevé, faible latence et haute densité (nombre de nœuds dans une seule machine). Cette méthode construit un index basé sur un graphe sur un ensemble de données à l'échelle du milliard SIFT-1B en utilisant une seule machine avec 64 Go de RAM et un CPU à 16 cœurs, atteignant 5000 QPS (requêtes par seconde) à plus de 95 % de rappel@1, et une latence moyenne inférieure à 3 ms.

Auteurs

Suhas Jayaram Subramanya: ancien employé de l'institut de recherche Microsoft India, doctorant à la CMU. Ses principaux domaines de recherche sont l'informatique à haute performance et les algorithmes d'apprentissage automatique pour les données à grande échelle.

Devvrit: Assistant de recherche diplômé à l'université du Texas à Austin. Ses recherches portent sur l'informatique théorique, l'apprentissage automatique et l'apprentissage profond.

Rohan Kadekodi: Doctorant à l'université du Texas. Ses recherches portent sur les systèmes et le stockage, notamment le stockage persistant, les systèmes de fichiers et le stockage kV.

Ravishankar Krishaswamy: Chercheur principal de l'institut de recherche indien de Microsoft. Docteur de la CMU. Ses recherches portent sur les algorithmes d'approximation basés sur les graphes et le regroupement.

Harsha Vardhan Simhadri: chercheur principal à l'institut de recherche indien de Microsoft. Docteur de la CMU. Dans le passé, il a étudié les algorithmes parallèles et les systèmes d'exécution. Aujourd'hui, son travail principal consiste à développer de nouveaux algorithmes et à écrire des modèles de programmation.

Motivations

La plupart des algorithmes ANNS courants font des compromis entre les performances de construction de l'index, les performances de recherche et le rappel. Les algorithmes basés sur les graphes, tels que HNSW et NSG, sont des méthodes de pointe en termes de performances de recherche et de rappel. Étant donné que la méthode d'indexation basée sur les graphes résidant en mémoire occupe trop de mémoire, il est relativement difficile d'indexer et de rechercher un ensemble de données à grande échelle à l'aide d'une seule machine disposant de ressources mémoire limitées.

De nombreuses applications exigent des réponses rapides de la méthode ANNS basée sur la distance euclidienne sur l'ensemble de données à l'échelle du milliard. Deux solutions principales sont présentées ci-dessous :

Index inversé + quantification : regroupement de l'ensemble de données en M partitions et compression de l'ensemble de données à l'aide de schémas de quantification tels que PQ (quantification par produit). Cette solution produit un faible rappel en raison d'une perte de précision causée par la compression des données. L'augmentation du topk permet d'améliorer le rappel, mais le QPS diminue en conséquence.
Diviser et indexer : diviser l'ensemble de données en plusieurs morceaux disjoints et construire un index en mémoire pour chaque morceau. Lorsque des requêtes sont formulées, la recherche est effectuée sur les index de chaque groupe et les résultats sont renvoyés après fusion. Cette solution entraîne une expansion excessive de l'échelle de l'ensemble de données et nécessite donc davantage de machines en raison de la restriction des ressources de mémoire sur une seule machine, ce qui se traduit par un faible QPS.

Les deux solutions mentionnées ci-dessus sont limitées par la restriction de mémoire d'une seule machine. Cet article propose la conception d'un mécanisme d'indexation résidant dans le SSD pour résoudre ce problème. Le défi de l'indexation résidant sur le SSD est de réduire le nombre d'accès aléatoires au disque et le nombre de demandes d'accès au disque.

Contributions

Cet article présente un schéma ANNS résidant sur le SSD, appelé DiskANN, qui peut prendre en charge efficacement la recherche sur des ensembles de données à grande échelle. Ce schéma est basé sur un algorithme basé sur un graphe présenté dans cet article : Vamana. Les contributions de cet article sont les suivantes :

DiskANN peut indexer et rechercher un ensemble de données d'un milliard de dimensions sur une seule machine dotée de 64 Go de RAM, avec un taux de rappel de plus de 95 %@1 et des temps de latence inférieurs à 5 millisecondes.
Un nouvel algorithme basé sur les graphes, appelé Vamana, avec un rayon de recherche plus petit que ceux de NSG et HNSW, a été proposé pour minimiser le nombre d'accès au disque.
Vamana peut fonctionner en mémoire et ses performances ne sont pas inférieures à celles de NSG et HNSW.
Les index Vamana plus petits construits sur des partitions qui se chevauchent du grand ensemble de données peuvent être fusionnés en un seul graphe sans perte de connectivité.
Vamana peut être combiné avec des schémas de quantification tels que PQ. La structure du graphe et les données originales sont stockées sur le disque tandis que les données compressées sont conservées en mémoire.

Vamana

Cet algorithme est similaire à l'idée de NSG[2][4] (pour ceux qui ne comprennent pas NSG, veuillez vous référer à la référence [2], et si vous ne voulez pas lire de documents, vous pouvez vous référer à la référence [4]). Leur principale différence réside dans la stratégie d'élagage. Pour être précis, un commutateur alpha a été ajouté à la stratégie d'élagage du NSG. L'idée principale de la stratégie d'élagage du NSG est que le choix des voisins du point cible soit aussi diversifié que possible. Si le nouveau voisin est plus proche d'un voisin du point cible que du point cible, il n'est pas nécessaire d'ajouter ce point à l'ensemble des points voisins. En d'autres termes, pour chaque voisin du point cible, il ne peut y avoir d'autres points voisins dans le rayon environnant dist (point cible, point voisin). Cette stratégie d'élagage permet de contrôler efficacement le degré de sortie du graphe et est relativement radicale. Elle réduit l'empreinte mémoire de l'index, améliore la vitesse de recherche, mais réduit également la précision de la recherche. La stratégie d'élagage de Vamana consiste à contrôler librement l'échelle d'élagage par le biais du paramètre alpha. Le principe de fonctionnement consiste à multiplier la distance (un point voisin, un point candidat) dans la condition d'élagage avec un paramètre alpha (pas moins de 1). Ce n'est que lorsque la dist (point cible, un certain point candidat) est supérieure à la distance de référence élargie que la stratégie d'élagage est adoptée, en augmentant la tolérance d'exclusion mutuelle entre les voisins du point cible.

Le processus d'indexation de Vamana est relativement simple :

Initialiser un graphe aléatoire ;
Calculer le point de départ, qui est similaire au point de navigation du NSG. Il faut d'abord trouver le centroïde global, puis le point le plus proche du centroïde global comme point de navigation. La différence entre Vamana et NSG est que l'entrée de NSG est déjà un graphe du plus proche voisin, de sorte que les utilisateurs peuvent simplement effectuer une recherche approximative du plus proche voisin sur le point centroïde directement sur le graphe initial du voisin. Cependant, Vamana initialise un graphe de voisinage aléatoire, et les utilisateurs ne peuvent donc pas effectuer une recherche approximative directement sur le graphe aléatoire. Ils doivent effectuer une comparaison globale pour obtenir un point de navigation qui servira de point de départ aux itérations suivantes. L'objectif de ce point est de minimiser le rayon de recherche moyen ;
Effectuer une recherche approximative du plus proche voisin sur chaque point en se basant sur le graphe aléatoire initialisé et le point de départ de la recherche déterminé à l'étape 2, faire de tous les points sur le chemin de recherche les ensembles de voisins candidats et exécuter la stratégie d'élagage des arêtes en utilisant alpha = 1. Comme dans le cas du NSG, la sélection de l'ensemble de points sur la trajectoire de recherche à partir du point de navigation en tant qu'ensemble de voisins candidats augmentera certaines longues arêtes et réduira efficacement le rayon de recherche.
Ajuster alpha > 1 (le document recommande 1,2) et répéter l'étape 3. Alors que l'étape 3 est basée sur un graphe aléatoire des plus proches voisins, le graphe est de faible qualité après la première itération. Par conséquent, une autre itération est nécessaire pour améliorer la qualité du graphe, qui est très importante pour le taux de rappel.

Cet article compare les trois index de graphes, à savoir Vamana, NSG et HNSW. En termes d'indexation et de performances d'interrogation, Vamana et NSG sont relativement proches, et tous deux dépassent légèrement HNSW. Les données sont présentées dans la section "Expériences" ci-dessous.

2.png

Pour visualiser le processus de construction de l'index Vamana, l'article fournit un graphique dans lequel 200 points bidimensionnels sont utilisés pour simuler deux cycles d'itération. La première ligne utilise alpha = 1 pour découper les bords. On peut constater que la stratégie d'élagage est relativement radicale et qu'un grand nombre d'arêtes sont élaguées. Après avoir augmenté la valeur alpha et assoupli les conditions d'élagage, de nombreuses arêtes sont évidemment rajoutées. Dans le graphe final, un certain nombre de longues arêtes sont ajoutées. Cela permet de réduire efficacement le rayon de recherche.

DiskANN

Un ordinateur personnel doté de seulement 64 Go de mémoire ne pourrait même pas contenir un milliard de données brutes, sans parler de l'index construit à partir de ces données. Il y a deux défis à relever : 1. Comment indexer un ensemble de données à si grande échelle avec des ressources mémoire limitées ? 2. Comment calculer la distance lors d'une recherche si les données originales ne peuvent pas être chargées en mémoire ?

L'article propose les solutions suivantes :

Pour le premier défi : tout d'abord, diviser les données en k grappes à l'aide des k-moyennes, puis affecter chaque point aux i grappes les plus proches. Généralement, 2 est suffisant pour le nombre i. Construire un index Vamana basé sur la mémoire pour chaque grappe, et finalement fusionner k index Vamana en un seul.
Pour le deuxième défi : construire un index sur les vecteurs originaux et interroger les vecteurs compressés. La création d'index sur le vecteur original garantit la qualité du graphique, tandis que le vecteur compressé peut être chargé dans la mémoire pour une recherche à gros grain. Bien que la recherche avec les vecteurs compressés puisse entraîner une perte de précision, la direction générale sera correcte tant que la qualité du graphique est suffisante. Le résultat final de la distance sera calculé en utilisant le vecteur original.

La disposition de l'index de DiskANN est similaire à celle des index de graphes généraux. L'ensemble des voisins de chaque point et les données vectorielles d'origine sont stockés ensemble. Cela permet de mieux utiliser la localité des données.

Comme indiqué précédemment, si les données d'index sont stockées sur le SSD, le nombre d'accès au disque et les requêtes de lecture et d'écriture du disque doivent être réduits autant que possible pour garantir un faible délai de recherche. DiskANN propose donc deux stratégies d'optimisation :

Cache hotspot : mettre en cache tous les points situés à moins de C sauts du point de départ dans la mémoire. Il est préférable de fixer la valeur de C entre 3 et 4.
Recherche par faisceau : En termes simples, il s'agit de précharger les informations sur les voisins. Lors de la recherche d'un point p, le point voisin de p doit être chargé à partir du disque s'il n'est pas en mémoire. Étant donné qu'une petite opération d'accès aléatoire au disque SSD prend à peu près le même temps qu'une opération d'accès à un seul secteur du disque SSD, les informations de voisinage de W points non accédés peuvent être chargées à la fois. W ne peut être ni trop grand ni trop petit. Un grand W gaspillera les ressources informatiques et la bande passante du SSD, tandis qu'un petit W augmentera le délai de recherche.

Expérience

L'expérience se compose de trois groupes :

Comparaison entre les index basés sur la mémoire : Vamana VS. NSG VS. HNSW

Ensembles de données : SIFT1M (128 dimensions), GIST1M (960 dimensions), DEEP1M (96 dimensions) et un ensemble de données de 1M échantillonné aléatoirement à partir de DEEP1B.

Paramètres de l'index (tous les ensembles de données utilisent le même ensemble de paramètres) :

HNSW：M = 128, efc = 512.

Vamana : R = 70, L = 75, alpha = 1,2.

NSG : R = 60, L = 70, C= 500.

Les paramètres de recherche ne sont pas fournis dans le document, ce qui peut être cohérent avec les paramètres d'indexation. Pour la sélection des paramètres, les paramètres de NSG mentionnés dans l'article sont basés sur les paramètres listés dans le dépôt GitHub de NSG afin de sélectionner le groupe le plus performant. Vamana et NSG étant relativement proches, les paramètres sont également proches. Cependant, la raison de la sélection des paramètres de HNSW n'est pas donnée. Nous pensons que le paramètre M de HNSW est relativement élevé. La comparaison entre les index basés sur les graphes risque d'être moins convaincante si leurs degrés extérieurs ne sont pas fixés au même niveau.

Avec les paramètres d'indexation ci-dessus, le temps d'indexation de Vamana, HNSW et NSG est respectivement de 129s, 219s et 480s. Le temps d'indexation de NSG inclut le temps de construction du graphe de voisinage initial avec EFANN [3].

Courbe de rappel-QPS :

3.png

La figure 3 montre que Vamana a d'excellentes performances sur les trois ensembles de données, similaires à celles de NSG et légèrement supérieures à celles de HNSW.

Comparaison du rayon de recherche :

La figure 2.c montre que Vamana a le chemin de recherche moyen le plus court pour un taux de rappel identique à celui de NSG et HNSW.

Comparaison entre un index construit en une seule fois et un grand index fusionné

Ensemble de données : SIFT1B

Paramètres de l'index construit en une seule fois : L = 50, R = 128, alpha = 1,2. Après avoir fonctionné pendant 2 jours sur une machine DDR3 de 1800 G, la mémoire maximale est d'environ 1100 G, et le degré de sortie moyen est de 113,9.

Procédure d'indexation basée sur la fusion :

Former 40 clusters sur l'ensemble de données à l'aide de kmeans ;
Chaque point est distribué dans les 2 clusters les plus proches ;
Construire un index Vamana avec L = 50, R = 64, et alpha = 1.2 pour chaque cluster ;
Fusionner les index de chaque cluster.

Cet index a généré un index de 384 Go avec un degré moyen de 92,1. Cet index a fonctionné pendant 5 jours sur une machine DDR4 de 64 Go.

Les résultats de la comparaison sont les suivants (figure 2a) : 4.png

En conclusion :

L'index construit en une seule fois est nettement meilleur que l'index basé sur la fusion ;
L'index basé sur la fusion est également excellent ;
Le schéma d'indexation basé sur la fusion est également applicable à l'ensemble de données DEEP1B (figure 2b).

Index basé sur le disque : DiskANN VS. FAISS VS. IVF-OADC+G+P

IVFOADC+G+P est un algorithme proposé dans la référence [5].

Ce document compare uniquement DiskANN à IVFOADC+G+P, car la référence [5] a prouvé qu'IVFOADC+G+P est meilleur que FAISS. En outre, FAISS nécessite des ressources GPU, qui ne sont pas prises en charge par toutes les plateformes.

IVF-OADC+G+P semble être une combinaison de HNSW et IVF-PQ. Il détermine les grappes à l'aide de HNSW et effectue la recherche en ajoutant certaines stratégies d'élagage à la grappe cible.

Le résultat est présenté à la figure 2a. Les chiffres 16 et 32 de la figure correspondent à la taille du livre de codes. L'ensemble de données est SIFT1B, quantifié par OPQ.

Détails de la mise en œuvre du code

Le code source de DiskANN est disponible en libre accès sur https://github.com/microsoft/DiskANN.

En janvier 2021, le code source de la solution de disque a été mis en libre accès.

Les paragraphes suivants présentent principalement le processus d'indexation et le processus de recherche.

Construction de l'index

Il existe 8 paramètres pour la construction d'un index :

data_type : les options incluent float/int8/uint8.

fichier_données.bin : Le fichier binaire des données d'origine. Les deux premiers entiers du fichier représentent respectivement le nombre total n du vecteur du jeu de données et la dimension du vecteur dim. Les n derniers octets de dim sizeof(data_type) sont des données vectorielles continues.

index_prefix_path : Le préfixe du chemin du fichier de sortie. Une fois l'index construit, plusieurs fichiers liés à l'index seront générés. Ce paramètre est le préfixe commun du répertoire dans lequel ils sont stockés.

R : Le degré de sortie maximal de l'index global.

L : Le paramètre L de l'index Vamana, la limite supérieure de la taille de l'ensemble des candidats.

B : Le seuil de mémoire lors de l'interrogation. Il contrôle la taille du livre de codes PQ, en Go.

M : Le seuil de mémoire lors de la construction d'un index. Il détermine la taille du fragment, en Go.

T : Le nombre de threads.

Processus d'indexation (fonction d'entrée : aux_utils.cpp::build_disk_index) :

Génère divers noms de fichiers de sortie en fonction de index_prefix_path.
Vérification des paramètres.
Lecture des méta du fichier data_file.bin pour obtenir n et dim. Déterminer le nombre de sous-espaces de codebook m de PQ en fonction de B et n.
générer_pq_pivots : Échantillonne le point central de l'ensemble d'apprentissage PQ en utilisant le taux d'échantillonnage de p = 1500000/n uniformément pour entraîner PQ globalement.
générer_pq_données_de_pivots : Génère un codebook PQ global et enregistre le point central et le codebook séparément.
build_merged_vamana_index : découpe l'ensemble de données original, construit des index Vamana par segments, et finalement fusionne les index en un seul.

partition_with_ram_budget : Déterminer le nombre de fragments k en fonction du paramètre M. Échantillonner l'ensemble de données à l'aide de kmeans, en répartissant chaque point entre les deux groupes les plus proches. Fragmentez l'ensemble de données et chaque fragment produit deux fichiers : un fichier de données et un fichier d'identification. Le fichier ID et le fichier de données correspondent l'un à l'autre, et chaque ID dans le fichier ID correspond à un vecteur dans le fichier de données. Les ID sont obtenus en numérotant chaque vecteur des données originales de 0 à n-1. L'ID est relativement important et est lié à la fusion.
- Échantillonner globalement et uniformément l'ensemble d'apprentissage avec un taux d'échantillonnage de 1500000 / n ;
- Initialiser num_parts = 3. Itérer à partir de 3 :
  - Effectuer num_parts-means++ sur l'ensemble d'apprentissage à l'étape i ;
  - Utilisez un taux d'échantillonnage de 0,01 pour échantillonner un ensemble de test de manière uniforme à l'échelle mondiale, et divisez l'ensemble de test en deux grappes les plus proches ;
  - Compter le nombre de points dans chaque grappe et le diviser par le taux d'échantillonnage pour estimer le nombre de points dans chaque grappe ;
  - Estimer la mémoire requise par la plus grande grappe à l'étape 3 en fonction de la taille de l'indice de Vamana, si elle ne dépasse pas le paramètre M, passer à l'étape iii, sinon num_parts ++ revenir à l'étape 2 ;
- Diviser l'ensemble de données d'origine en fichiers de groupe num_parts, chaque groupe de fichiers comprenant des fichiers de données fragmentées et des fichiers d'identification correspondant aux données fragmentées.
Créer des index Vamana séparément pour toutes les tranches de l'étape a et les sauvegarder sur disque ;
merge_shards : fusionner les tessons Vamana de num_parts en un index global :
- Lire le fichier ID des fragments num_parts dans idmap. Cet idmap est équivalent à l'établissement d'une correspondance directe fragment->id ;
- Établir une correspondance inverse de id-> fragments selon idmap, et savoir dans quels deux fragments se trouve chaque vecteur ;
- Utiliser un lecteur avec un cache de 1 Go pour ouvrir les index Vamana des tranches num_parts, et utiliser un rédacteur avec un cache de 1 Go pour ouvrir le fichier de sortie, prêt à être fusionné ;
- Placer les points de navigation num_parts de l'index Vamana dans le fichier de points centraux, qui sera utilisé lors de la recherche ;
- Commencer la fusion en fonction de l'ID, du plus petit au plus grand, lire l'ensemble des points voisins de chaque vecteur original dans chaque fragment à tour de rôle en fonction de la correspondance inverse, dédupliquer, mélanger, tronquer, et écrire dans le fichier de sortie. Étant donné que le découpage était à l'origine ordonné globalement et que la fusion est maintenant également ordonnée, l'ID dans l'index de vidange final et l'ID des données d'origine sont en correspondance biunivoque.
- Supprimez les fichiers temporaires, y compris les fichiers de fragments, les index de fragments et les fichiers d'identifiants de fragments.

créer une configuration de disque : L'index global généré à l'étape 6 n'a qu'une table d'adjacence compacte. Cette étape permet d'aligner l'index. La table d'adjacence et les données originales sont stockées ensemble. Lors d'une recherche, il convient de charger la table d'adjacence et de lire le vecteur original en même temps pour un calcul précis de la distance. Il existe également le concept de SECTEUR, dont la taille par défaut est de 4096. Chaque SECTEUR ne contient que 4096 / node_size informations vectorielles. node_size = taille d'un vecteur unique + taille d'une table d'adjacence d'un nœud unique.
Enfin, effectuez un échantillonnage uniforme global de 150000 / n, sauvegardez-le et utilisez-le pour vous échauffer lors de la recherche.

Recherche

Il existe 10 paramètres de recherche :

index_type : Les options incluent Float/int8/uint8, similaire au premier paramètre data_type lors de la construction d'un index.
index_prefix_path : Se réfère au paramètre d'index index_prefix_path.
num_nodes_to_cache : Nombre de points d'accès au cache.
num_threads : Nombre de fils de recherche.
beamwidth : limite supérieure du nombre de points de précharge. Le système détermine si elle est fixée à 0.
query_file.bin : Fichier d'ensemble de requêtes.
truthset.bin : Fichier de l'ensemble des résultats, "null" signifie que l'ensemble des résultats n'est pas fourni, le programme le calcule lui-même ;
K : topk ;
result_output_prefix : Chemin d'enregistrement des résultats de la recherche ;
L* : Liste des paramètres de recherche. Plusieurs valeurs peuvent être ajoutées. Pour chaque L, des informations statistiques seront données lors d'une recherche avec différents L.

Processus de recherche :

Chargement des données connexes : chargement de l'ensemble des requêtes, des données relatives au point central du PQ, des données du livre de codes, du point de départ de la recherche et d'autres données, et lecture des méta-index.
Utiliser l'ensemble de données échantillonné pendant l'indexation pour effectuer la recherche par faisceau en cache, compter les temps d'accès de chaque point et charger les points num_nodes_to_cache ayant la fréquence d'accès la plus élevée dans le cache.
Il y a une opération WARMUP par défaut. Comme à l'étape 2, cet échantillon de données est également utilisé pour effectuer une recherche de faisceaux en cache.
En fonction du nombre de paramètres L donnés, chaque L sera exécuté avec cached_beam_search à nouveau avec l'ensemble de requêtes, et des statistiques telles que le taux de rappel et le QPS seront produites. Le processus d'échauffement et les statistiques sur les données des hotspots ne sont pas comptabilisés dans le temps d'interrogation.

À propos de cached_beam_search :

Trouver le candidat le plus proche du point d'interrogation à partir du point de départ du candidat. La distance PQ est utilisée ici, et le point de départ est ajouté à la file d'attente de recherche.
Commencer la recherche :

Dans la file d'attente de recherche, il n'y a pas plus de beam_width + 2 points non visités. Si ces points se trouvent dans le cache, ils sont ajoutés à la file d'attente des résultats du cache. S'ils ne le sont pas, ils sont ajoutés à la file d'attente des erreurs. Veillez à ce que la taille de la file d'attente ne dépasse pas beam_width.
Envoyez des demandes d'accès au disque asynchrones aux points de la file d'attente des erreurs.
Pour les points touchés par le cache, utilisez les données originales et les données de la requête pour calculer la distance exacte, ajoutez-les à la file d'attente des résultats, puis utilisez PQ pour calculer la distance avec les points voisins qui n'ont pas été visités avant de les ajouter à la file d'attente de recherche. La longueur de la file d'attente de recherche est limitée par des paramètres.
Traiter les points manquants mis en cache à l'étape a, comme à l'étape c.
Lorsque la file d'attente de recherche est vide, la recherche se termine et la file d'attente de résultats topk est renvoyée.

Résumé

Bien que ce travail soit relativement long, il est globalement excellent. Les idées du document et du code sont claires : diviser un certain nombre d'ensembles qui se chevauchent à l'aide de k-moyennes, puis diviser les ensembles pour construire un index de carte, et enfin fusionner les index, ce qui est une idée relativement nouvelle. Quant à l'index graphique Vamana basé sur la mémoire, il s'agit essentiellement d'une version initialisée de manière aléatoire de NSG qui peut contrôler la granularité du découpage. Lors des requêtes, il utilise pleinement le cache et le pipeline, couvre une partie du temps d'entrée et de sortie et améliore le QPS. Toutefois, selon l'article, même si l'état de la machine n'est pas extraordinaire, le temps de formation peut prendre jusqu'à 5 jours et la facilité d'utilisation est relativement faible. Des optimisations de la formation sont certainement nécessaires à l'avenir. Du point de vue du code, la qualité est relativement élevée et peut être directement utilisée dans l'environnement de production.