HNSW
Hierarchical Navigable Small World — l'algorithme dominant à base de graphe pour la recherche approximative du plus proche voisin parmi des vecteurs. Construit un graphe « petit monde » multicouche où la recherche saute du grossier au fin. Rapide et précis, mais gourmand en mémoire.
Mécanique : les vecteurs sont reliés dans un graphe où chaque nœud a des voisins ; la couche supérieure est clairsemée (grands sauts), la couche inférieure dense (affinage). Une recherche démarre en haut, « glisse » vers la cible et s'affine en descendant → temps de recherche logarithmique. Les paramètres M (voisins par nœud) et ef (largeur de recherche) pilotent le compromis vitesse/mémoire/précision. Avantage : excellent rappel à haute vitesse, insertions incrémentales possibles. Contrepartie : forte consommation mémoire, tout le graphe devant tenir en RAM, et construction plus coûteuse qu'IVF. Choix par défaut dans pgvector, Qdrant, Weaviate et FAISS pour la plupart des charges de travail. Se distingue d'IVFFlat, basé sur des clusters, moins gourmand en mémoire mais généralement moins précis. Le type d'index vectoriel le plus courant en 2024.