HNSWLib est une bibliothèque C++ composée uniquement de fichiers d'en-tête qui implémente l'algorithme Hierarchical Navigable Small World (HNSW) pour la recherche approximative du plus proche voisin. La bibliothèque est conçue pour trouver des éléments similaires à un élément de requête dans de grandes collections de données vectorielles sans comparer la requête à chaque élément individuellement. Elle est couramment utilisée dans les systèmes de apprentissage automatique, les applications d'intelligence artificielle et les bases de données vectorielles où la vitesse et l'évolutivité sont essentielles.
L'algorithme HNSW, que HNSWLib implémente, stocke les vecteurs dans une structure de graphe à plusieurs couches. Chaque vecteur devient un nœud, et des liens le connectent aux vecteurs voisins. Les couches supérieures contiennent moins de nœuds et agissent comme une carte grossière, tandis que la couche inférieure contient tous les nœuds pour une recherche détaillée. Une recherche commence dans une couche supérieure, suit les liens vers des nœuds plus proches de la requête, puis répète le processus dans les couches inférieures jusqu'à ce qu'elle identifie un ensemble de voisins les plus probables.
Contexte
Le problème de la recherche du plus proche voisin consiste à déterminer quels éléments d'un ensemble de données sont les plus proches d'un élément de requête. Une recherche directe compare la requête à chaque élément, ce qui devient lent pour les grands ensembles de données. Les méthodes exactes utilisant des arbres spatiaux comme l'arbre k-d ou l'arbre R perdent en efficacité dans les données à haute dimension en raison de la malédiction de la dimensionnalité. Les méthodes approximatives du plus proche voisin échangent l'exactitude contre la vitesse, renvoyant rapidement des éléments proches plutôt que de garantir le plus proche absolu.
HNSW s'appuie sur la recherche sur les réseaux à petit monde et les graphes navigables. Dans les graphes à petit monde, la plupart des nœuds se connectent par de courtes chaînes de liens. Les travaux de Jon Kleinberg sur la navigation dans les réseaux à petit monde ont influencé les recherches ultérieures sur l'ajout de liens qui rendent les graphes plus faciles à naviguer de manière gloutonne. L'algorithme HNSW étend les méthodes antérieures de petit monde navigable en ajoutant une hiérarchie de couches de graphe, ce qui aide à trouver une bonne région avant une recherche détaillée.
Algorithme
HNSWLib utilise un graphe de proximité où les vecteurs voisins sont connectés par des arêtes. L'algorithme se déplace dans l'ensemble de données en utilisant ces arêtes plutôt qu'en parcourant chaque vecteur. Le graphe est hiérarchique : chaque vecteur apparaît dans la couche inférieure, tandis que certains vecteurs apparaissent également dans des couches supérieures avec moins de vecteurs à mesure que les couches montent. Les couches supérieures permettent des déplacements à longue portée, tandis que les couches inférieures permettent une recherche détaillée près des candidats prometteurs.
Une recherche typique commence à partir d'un point d'entrée dans la couche la plus élevée. À chaque étape, l'algorithme examine les nœuds voisins et se déplace vers celui qui est plus proche de la requête. Lorsqu'aucun voisin plus proche n'existe dans cette couche, il descend à la couche suivante. Dans la couche inférieure, il explore un ensemble de candidats plus large et renvoie les candidats les plus proches trouvés. Cette navigation gloutonne choisit à plusieurs reprises des nœuds localement meilleurs pour s'approcher du point de requête.
Construction et paramètres
Le graphe HNSW est construit de manière incrémentale. Lors de l'insertion d'un nouveau vecteur, l'algorithme lui attribue une couche maximale, recherche les nœuds existants voisins et connecte le nouveau nœud aux voisins sélectionnés dans chaque couche où il apparaît. Les implémentations exposent des paramètres contrôlant les compromis entre vitesse, précision, utilisation de la mémoire et temps de construction. Des connexions de graphe plus élevées améliorent le rappel mais nécessitent plus de mémoire. Des listes de candidats de recherche plus grandes améliorent la précision mais ralentissent les requêtes. Des listes de candidats de construction plus grandes améliorent la qualité du graphe mais ralentissent la construction de l'index.
Parce que HNSW est approximatif, les résultats peuvent différer des recherches exactes. La performance pratique dépend des caractéristiques de l'ensemble de données, de la mesure de distance, de la qualité de l'implémentation et des paramètres. Des études de référence ont montré que les bibliothèques basées sur HNSW sont de solides performeurs parmi les méthodes approximatives du plus proche voisin, bien que la performance dans le pire des cas puisse différer des résultats de référence courants.
Utilisation dans les systèmes de recherche vectorielle
HNSWLib est utilisé comme index dans les systèmes qui stockent et recherchent des vecteurs à haute dimension, y compris les bases de données vectorielles, les moteurs de recherche et les extensions de bases de données. Les applications typiques incluent la recherche sémantique, les systèmes de recommandation, la recherche de similarité d'images et la génération augmentée par récupération. La bibliothèque est associée aux auteurs originaux de HNSW et est largement adoptée dans les environnements de production.
Plusieurs projets logiciels implémentent ou prennent en charge HNSW. Les bibliothèques incluent HNSWLib et FAISS. Les systèmes de bases de données et de recherche documentant le support HNSW incluent Apache Lucene, Chroma, ClickHouse, DuckDB, MariaDB, Milvus, pgvector, Qdrant et Redis. Ces systèmes exploitent HNSW pour une recherche approximative rapide dans des applications allant de la récupération de modèles de langage de grande taille aux pipelines de IA générative.
Voir aussi
- Recherche approximative du plus proche voisin
- Base de données vectorielle
- Hachage sensible à la localité
- Quantification de produits