DiskANN : une solution ANNS basée sur disque avec un rappel élevé et un QPS élevé sur un jeu de données à l’échelle du milliard
« DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node » est un article publié à NeurIPS en 2019. L’article présente une méthode de pointe pour effectuer la construction d’index et la recherche sur un jeu de données à l’échelle du milliard en utilisant une seule machine avec seulement 64 Go de RAM et un SSD suffisamment grand. De plus, elle satisfait aux trois exigences de l’ANNS (Approximate Nearest Neighbor Search) sur les jeux de données à grande échelle : rappel élevé, faible latence et haute densité (nombre de nœuds sur une seule machine). Cette méthode construit un index basé sur un graphe sur un jeu 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) avec plus de 95 % de recall@1, et une latence moyenne inférieure à 3 ms.
Auteurs
Suhas Jayaram Subramanya : ancien employé de Microsoft India Research Institute, doctorant à CMU. Ses principaux intérêts de recherche sont le calcul haute performance et les algorithmes d’apprentissage automatique pour les données à grande échelle.
Devvrit : assistant de recherche diplômé à The University of Texas at Austin. Ses intérêts de recherche sont l’informatique théorique, l’apprentissage automatique et l’apprentissage profond.
Rohan Kadekodi : doctorant à l’Université du Texas. Son domaine de recherche est les systèmes et le stockage, incluant principalement le stockage persistant, les systèmes de fichiers et le stockage kV.
Ravishankar Krishaswamy : chercheur principal au Microsoft Indian Research Institute. Docteur de CMU. Son domaine de recherche est l’algorithme d’approximation basé sur les graphes et le clustering.
Harsha Vardhan Simhadri : chercheur principal au Microsoft Indian Research Institute. Docteur de CMU. Par le passé, il a étudié les algorithmes parallèles et les systèmes d’exécution. À présent, son travail principal consiste à développer de nouveaux algorithmes et à écrire des modèles de programmation.
Motivations
La plupart des algorithmes ANNS courants font certains compromis entre les performances de construction d’index, les performances de recherche et le rappel. Les algorithmes basés sur des graphes tels que HNSW et NSG sont actuellement des méthodes de pointe en matière de performances de recherche et de rappel. Comme la méthode d’indexation basée sur des graphes résidant en mémoire occupe trop de mémoire, il est relativement difficile d’indexer et de rechercher un jeu de données à grande échelle en utilisant une seule machine disposant de ressources mémoire limitées.
De nombreuses applications nécessitent des réponses rapides pour l’ANNS basée sur la distance euclidienne sur des jeux de données à l’échelle du milliard. Voici deux solutions principales :
Index inversé + quantification : regrouper le jeu de données en M partitions et compresser le jeu de données à l’aide de schémas de quantification tels que PQ (Product Quantization). Cette solution produit un faible rappel en raison d’une perte de précision causée par la compression des données. Augmenter le topk aide à améliorer le rappel, tandis que le QPS diminuerait en conséquence.
Diviser et indexer : diviser le jeu de données en plusieurs fragments disjoints et construire un index en mémoire pour chaque fragment. Lorsque les requêtes arrivent, la recherche est effectuée sur les index de chaque fragment et les résultats sont renvoyés après fusion. Cette solution provoque une surexpansion de l’échelle du jeu de données, et donc davantage de machines sont nécessaires en raison de la restriction des ressources mémoire sur une seule machine, ce qui entraîne 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 sur SSD pour résoudre ce problème. Le défi de l’indexation résidant sur SSD est de réduire le nombre d’accès disque aléatoires et le nombre de requêtes d’accès au disque.
Contributions
Cet article présente un schéma ANNS résidant sur SSD appelé DiskANN, qui peut prendre efficacement en charge la recherche sur des jeux de données à grande échelle. Ce schéma est basé sur un algorithme fondé sur les graphes présenté dans cet article : Vamana. Les contributions de cet article incluent :
DiskANN peut indexer et rechercher un jeu de données à l’échelle du milliard de plus de 100 dimensions sur une seule machine avec 64 Go de RAM, fournissant plus de 95 % de recall@1 avec des latences inférieures à 5 millisecondes.
Un nouvel algorithme basé sur des graphes, appelé Vamana, avec un rayon de recherche plus petit que ceux de NSG et HNSW, a été proposé afin de minimiser le nombre d’accès au disque.
Vamana peut fonctionner en mémoire et ses performances ne sont pas plus lentes que celles de NSG et HNSW.
Les index Vamana plus petits construits sur des partitions chevauchantes du grand jeu de données peuvent être fusionnés en un seul graphe sans perdre la 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 reporter à la référence [2], et si vous ne souhaitez pas lire d’articles, vous pouvez vous reporter à 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 de NSG. L’idée principale de la stratégie d’élagage de 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, nous n’avons pas besoin d’ajouter ce point à l’ensemble des points voisins. En d’autres termes, pour chaque voisin du point cible, il ne peut y avoir aucun autre point voisin dans le rayon environnant dist (point cible, point voisin). Cette stratégie d’élagage contrôle efficacement le degré sortant 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’ampleur de l’élagage au moyen du paramètre alpha. Le principe de fonctionnement consiste à multiplier la dist (un point voisin, point candidat) dans la condition d’élagage par un paramètre alpha (non inférieur à 1). Ce n’est que lorsque la dist (point cible, un certain point candidat) est supérieure à la distance de référence agrandie que la stratégie d’élagage est adoptée, ce qui augmente la tolérance de l’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 de NSG. Tout d’abord, trouver le centroïde global, puis trouver 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 des plus proches voisins, de sorte que les utilisateurs peuvent simplement effectuer une recherche approximative du plus proche voisin sur le point centroïde directement sur le graphe de voisins initial. Cependant, Vamana initialise un graphe aléatoire des plus proches voisins ; les utilisateurs ne peuvent donc pas effectuer de recherche approximative directement sur le graphe aléatoire. Ils doivent effectuer une comparaison globale pour obtenir un point de navigation comme point de départ des itérations ultérieures. 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 fonction du graphe de voisins aléatoire initialisé et du point de départ de recherche déterminé à l’étape 2, faire de tous les points du chemin de recherche les ensembles de voisins candidats, et exécuter la stratégie d’élagage des arêtes avec alpha = 1. Comme pour NSG, sélectionner l’ensemble de points sur le chemin de recherche à partir du point de navigation comme ensemble de voisins candidats ajoutera certaines arêtes longues et réduira efficacement le rayon de recherche.
Ajuster alpha > 1 (l’article 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. Une autre itération est donc nécessaire pour améliorer la qualité du graphe, ce qui est très important pour le taux de rappel.
Cet article compare les trois index de graphes, à savoir Vamana, NSG et HNSW. En termes de performances d’indexation et de requête, Vamana et NSG sont relativement proches, et tous deux surpassent légèrement HNSW. Reportez-vous à la section Expérience ci-dessous pour les données.
Figure 1.
Pour visualiser le processus de construction de l’index Vamana, l’article fournit un graphe dans lequel 200 points bidimensionnels sont utilisés pour simuler deux cycles d’itération. La première ligne utilise alpha = 1 pour élaguer les arêtes. On peut voir 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, beaucoup d’arêtes sont manifestement réajoutées. Dans le graphe final, un nombre assez important de longues arêtes est ajouté. Cela peut 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 d’éléments de données brutes, sans parler de l’index construit sur celles-ci. Deux défis se posent : 1. Comment indexer un ensemble de données à si grande échelle avec des ressources mémoire limitées ? 2. Comment calculer la distance lors de la recherche si les données originales ne peuvent pas être chargées en mémoire ?
L’article a proposé les solutions suivantes :
Pour le premier défi : tout d’abord, diviser les données en k clusters à l’aide de k-means, puis affecter chaque point aux i clusters les plus proches. Généralement, 2 suffit pour le nombre i. Construire un index Vamana en mémoire pour chaque cluster, puis fusionner finalement les k index Vamana en un seul.
Pour le second défi : construire l’index sur les vecteurs originaux et interroger des vecteurs compressés. Construire les index sur le vecteur original garantit la qualité du graphe, tandis que le vecteur compressé peut être chargé en mémoire pour une recherche grossière. 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 graphe est suffisamment élevée. Le résultat final de distance sera calculé à l’aide du 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 du vecteur original sont stockés ensemble. Cela permet de mieux exploiter la localité des données.
Comme mentionné précédemment, si les données d’index sont stockées sur le SSD, le nombre d’accès disque et les requêtes de lecture et d’écriture disque doivent être réduits autant que possible afin de garantir un faible délai de recherche. Par conséquent, DiskANN propose deux stratégies d’optimisation :
Cache des points chauds : mettre en cache en mémoire tous les points situés à moins de C sauts du point de départ. Il est préférable de définir la valeur de C entre 3 et 4.
Recherche par faisceau : pour faire simple, il s’agit de précharger les informations des voisins. Lors de la recherche du point p, le point voisin de p doit être chargé depuis le disque s’il n’est pas en mémoire. Puisqu’un petit nombre d’opérations d’accès aléatoire au SSD prend à peu près le même temps qu’une opération d’accès à un seul secteur SSD, les informations des voisins de W points non consultés peuvent être chargées en une fois. W ne doit pas être défini trop grand ni trop petit. Un W élevé gaspillera des ressources de calcul et de la bande passante SSD, tandis qu’un W faible augmentera le délai de recherche.
Expérience
L’expérience se compose de trois groupes :
Comparaison entre les index en 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 d’index (tous les ensembles de données utilisent le même jeu 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 l’article, 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 offrant les meilleures performances. Vamana et NSG sont relativement proches, les paramètres sont donc également définis de manière proche. Cependant, la raison du choix des paramètres de HNSW n’est pas donnée. Nous pensons que le paramètre M de HNSW est défini relativement haut. Cela pourrait rendre la comparaison entre les index basés sur des graphes moins convaincante si leurs degrés sortants ne sont pas définis au même niveau.
Sous les paramètres d’indexation ci-dessus, les temps d’indexation de Vamana, HNSW et NSG sont respectivement de 129 s, 219 s et 480 s. Le temps d’indexation de NSG inclut le temps nécessaire pour construire le graphe initial de voisins avec EFANN [3].
Courbe Recall-QPS :
Figure 2.
On peut voir sur la Figure 3 que Vamana présente d’excellentes performances sur les trois jeux de données, similaires à celles de NSG et légèrement meilleures que celles de HNSW.
Comparaison du rayon de recherche :
D’après la Figure 2.c, nous pouvons voir que Vamana présente le chemin de recherche moyen le plus court pour le même taux de rappel, comparé à ceux de NSG et HNSW.
Comparaison entre un index construit en une seule fois et un grand index fusionné
Jeu de données : SIFT1B
Paramètres de l’index construit en une seule fois : L = 50, R = 128, alpha = 1.2. Après une exécution de 2 jours sur une machine DDR3 de 1800 G, la mémoire maximale est d’environ 1100 G, et le degré sortant moyen est de 113.9.
Procédure d’indexation basée sur la fusion :
Entraîner 40 clusters sur le jeu 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é sortant moyen de 92.1. Cet index a fonctionné pendant 5 jours sur une machine DDR4 de 64 Go.
Les résultats de comparaison sont les suivants (Figure 2a) :
Figure 3.
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 au jeu de données DEEP1B (Figure 2b).
Index basé sur disque : DiskANN VS. FAISS VS. IVF-OADC+G+P
IVFOADC+G+P est un algorithme proposé dans la Référence [5].
Cet article compare uniquement DiskANN avec IVFOADC+G+P, puisque la référence [5] a prouvé que IVFOADC+G+P est meilleur que FAISS. De plus, 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 clusters à l’aide de HNSW et effectue la recherche en ajoutant certaines stratégies d’élagage au cluster cible.
Le résultat est présenté dans la Figure 2a. Les valeurs 16 et 32 dans la figure correspondent à la taille du codebook. Le jeu de données est SIFT1B, quantifié par OPQ.
Détails d’implémentation du code
Le code source de DiskANN est open source sur https://github.com/microsoft/DiskANN
En janvier 2021, le code source de la solution disque a été rendu open source.
Ce qui suit présente principalement le processus d’indexation et le processus de recherche.
Construction de l’index
Il y a 8 paramètres pour construire l’index :
data_type: les options incluent float/int8/uint8.
data_file.bin: Le fichier binaire de données d’origine. Les deux premiers entiers du fichier représentent respectivement le nombre total n de vecteurs du jeu de données et la dimension vectorielle dim. Les derniers n * dim * sizeof(data_type) octets sont des données vectorielles continues.
index_prefix_path: Le préfixe de 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 où ils sont stockés.
R: Le degré sortant maximal de l’index global.
L: Le paramètre L de l’index Vamana, la borne supérieure de la taille de l’ensemble candidat.
B: Le seuil de mémoire lors de l’interrogation. Il contrôle la taille du codebook 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érer divers noms de fichiers de sortie selon index_prefix_path.
Vérification des paramètres.
Lire les métadonnées de data_file.bin pour obtenir n et dim. Déterminer le nombre m de sous-espaces du codebook de PQ selon B et n.
generate_pq_pivots: Échantillonner le point central de l’ensemble d’entraînement PQ en utilisant uniformément le taux d’échantillonnage p = 1500000/n pour entraîner PQ globalement.
generate_pq_data_from_pivots: Générer le codebook PQ global et enregistrer séparément le point central et le codebook.
build_merged_vamana_index : découper l'ensemble de données original, construire des index Vamana par segments, puis fusionner les index en un seul.
partition_with_ram_budget : Déterminer le nombre de fragments k selon le paramètre M. Échantillonner l'ensemble de données avec kmeans, en répartissant chaque point dans les deux clusters les plus proches. Fragmenter l'ensemble de données, et chaque fragment produit deux fichiers : un fichier de données et un fichier d'ID. Le fichier d'ID et le fichier de données se correspondent, et chaque ID dans le fichier d'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'entraînement 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'entraînement à l'étape i ;
- Utiliser un taux d'échantillonnage de 0.01 pour échantillonner un ensemble de test uniformément à l'échelle globale, et diviser l'ensemble de test entre les 2 clusters les plus proches ;
- Compter le nombre de points dans chaque cluster et le diviser par le taux d'échantillonnage pour estimer le nombre de points dans chaque cluster ;
- Estimer la mémoire requise par le plus grand cluster à l'étape 3 selon la taille de l'index Vamana ; si elle ne dépasse pas le paramètre M, passer à l'étape iii, sinon num_parts ++ et revenir à l'étape 2 ;
Diviser l'ensemble de données original en num_parts groupes de fichiers, chaque groupe de fichiers incluant des fichiers de données fragmentées et des fichiers d'ID correspondant aux données fragmentées.
Créer des index Vamana séparément pour toutes les tranches de l'étape a et les enregistrer sur le disque ;
merge_shards : fusionner num_parts fragments Vamana en un index global :
Lire le fichier d'ID de num_parts fragments dans idmap. Cet idmap équivaut à établir 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 1 Go de cache pour ouvrir les index Vamana des num_parts tranches, et utiliser un writer avec 1 Go de cache pour ouvrir le fichier de sortie, prêt pour la fusion ;
Placer les num_parts points de navigation de l'index Vamana dans le fichier de points centraux, qui sera utilisé lors de la recherche ;
Commencer la fusion selon les ID du plus petit au plus grand, lire à tour de rôle l'ensemble des points voisins de chaque vecteur original dans chaque fragment selon la correspondance inverse, dédupliquer, mélanger, tronquer et écrire dans le fichier de sortie. Comme le découpage était initialement globalement ordonné, et que la fusion se fait maintenant également dans l'ordre, l'ID dans l'index final vidé et l'ID des données originales sont en correspondance un à un.
Supprimer les fichiers temporaires, y compris les fichiers de fragments, les index de fragments et les fichiers d'ID de fragments.
7.create_disk_layout : L'index global généré à l'étape 6 ne contient qu'une table d'adjacence compacte. Cette étape sert à aligner l'index. La table d'adjacence et les données originales sont stockées ensemble. Lors de la recherche, charger la table d'adjacence et lire le vecteur original en même temps pour un calcul précis de la distance. Il existe aussi le concept de SECTOR, dont la taille par défaut est 4096. Chaque SECTOR ne contient que 4096 / node_size éléments d'informations vectorielles. node_size = taille d'un vecteur unique + taille de la table d'adjacence d'un nœud unique.
8.Enfin, effectuer un échantillonnage uniforme global de 150000 / n, l'enregistrer, et l'utiliser pour le warmup lors de la recherche.
Recherche
Il y a 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érer au paramètre d'index index_prefix_path.
num_nodes_to_cache : Nombre de points chauds du cache.
num_threads : Nombre de threads de recherche.
beamwidth : Limite supérieure du nombre de points préchargés. Le système détermine s'il est défini à 0.
query_file.bin : Fichier de l'ensemble de requêtes.
truthset.bin : Fichier de l'ensemble de résultats, "null" signifie que l'ensemble de résultats n'est pas fourni, le programme le calcule lui-même ;
K : topk ;
result_output_prefix : Chemin pour enregistrer les résultats de recherche ;
L*: Liste des paramètres de recherche. Plusieurs valeurs peuvent être ajoutées. Pour chaque L, des informations statistiques seront fournies lors de la recherche avec différents L.
Processus de recherche :
Charger les données associées : charger l’ensemble de requêtes, les données des points centraux PQ, les données du dictionnaire de codes, le point de départ de la recherche et d’autres données, et lire les métadonnées de l’index.
Utiliser l’ensemble de données échantillonné pendant l’indexation pour effectuer cached_beam_search, compter le nombre d’accès de chaque point, et charger dans le cache les num_nodes_to_cache points ayant la fréquence d’accès la plus élevée.
Il y a une opération WARMUP par défaut. Comme à l’étape 2, cet ensemble de données d’échantillon est également utilisé pour effectuer un cached_beam_search.
Selon le nombre de paramètres L fournis, chaque L sera à nouveau exécuté avec cached_beam_search sur l’ensemble de requêtes, et des statistiques telles que le taux de rappel et le QPS seront produites. Le processus de warmup et les données de points chauds statistiques ne sont pas comptés dans le temps de requête.
À propos de cached_beam_search :
Trouver le candidat le plus proche du point de requête à partir du point de départ candidat. La distance PQ est utilisée ici, et le point de départ est ajouté à la file de recherche.
Commencer la recherche :
À partir de la file de recherche, il n’y a pas plus de beam_width + 2 points non visités. Si ces points sont dans le cache, les ajouter à la file des succès de cache. S’ils ne sont pas trouvés, les ajouter à la file des échecs. S’assurer que la taille de la file des échecs ne dépasse pas beam_width.
Envoyer des requêtes asynchrones d’accès au disque aux points de la file des échecs.
Pour les points trouvés dans le cache, utiliser les données originales et les données de requête pour calculer la distance exacte, les ajouter à la file de résultats, puis utiliser PQ pour calculer la distance jusqu’aux points voisins qui n’ont pas encore été visités avant de les ajouter à la file de recherche. La longueur de la file de recherche est limitée par les paramètres.
Traiter les points d’échec de cache de l’étape a, de manière similaire à l’étape c.
Lorsque la file de recherche est vide, la recherche se termine, et le topk de la file de résultats est renvoyé.
Résumé
Bien qu’il s’agisse d’un travail relativement long, il est globalement excellent. Les idées de l’article et du code sont claires : diviser un certain nombre de buckets se chevauchant via k-means, puis diviser les buckets pour construire un index de carte, et enfin fusionner les index, ce qui est une idée relativement nouvelle. Quant à l’index de graphe en mémoire Vamana, il s’agit essentiellement d’une version initialisée aléatoirement de NSG qui peut contrôler la granularité de l’élagage. Lors des requêtes, il exploite pleinement cache + pipeline, masque une partie du temps d’E/S, et améliore le QPS. Cependant, selon l’article, même si la configuration de la machine n’est pas extraordinaire, le temps d’entraînement peut atteindre 5 jours, et l’utilisabilité est relativement faible. Des optimisations de l’entraînement seront certainement nécessaires à l’avenir. Du point de vue du code, la qualité est relativement élevée et il peut être directement utilisé dans un environnement de production.
Références
[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 and Deng Cai. GitHub - ZJULearning/efanna: fast library for ANN search and KNN graph construction.
Continuer à lire
Top 10 Context Engineering Techniques You Should Know for Production RAG
A practical guide to context engineering for production LLM systems, covering RAG, context processing, memory, agents, and multimodal context.
Similarity Metrics for Vector Search
Exploring five similarity metrics for vector search: L2 or Euclidean distance, cosine distance, inner product, and hamming distance.
Vector Databases vs. Hierarchical Databases
Use a vector database for AI-powered similarity search; use a hierarchical database for organizing data in parent-child relationships with efficient top-down access patterns.