Index HNSW (Hierarchical Navigable Small World)

Définition

L'index HNSW, pour Hierarchical Navigable Small World, est une structure de donnees utilisee par la recherche vectorielle approximee pour retrouver rapidement les voisins les plus proches d'un vecteur de requete au sein d'une base de donnees volumineuse. Son principe repose sur la construction d'un graphe multi-couches ou chaque vecteur est relie a un ensemble limite de voisins proches, les couches superieures du graphe contenant peu de noeuds relies par des connexions longues qui permettent de traverser rapidement l'espace vectoriel, tandis que les couches inferieures, plus denses, affinent progressivement la recherche jusqu'aux voisins exacts. Cette architecture en graphe navigable offre un excellent compromis entre vitesse de recherche et precision des resultats, avec une complexite de recherche approximativement logarithmique par rapport au nombre de vecteurs indexes, ce qui le rend tres performant meme sur des collections de plusieurs dizaines de millions d'elements. HNSW est aujourd'hui l'algorithme d'indexation par defaut de la plupart des bases de donnees vectorielles utilisees en production, comme Pinecone, Weaviate, Milvus ou l'extension pgvector de PostgreSQL. Son principal inconvenient est une consommation memoire elevee, le graphe entier devant generalement etre maintenu en memoire vive pour offrir des temps de reponse compatibles avec les applications RAG en temps reel, ce qui constitue un critere de dimensionnement important lors du choix d'une infrastructure de recherche vectorielle.