Recherche vectorielle approximee ANN (Approximate Nearest Neighbor)

Définition

La recherche vectorielle approximee, ou ANN pour Approximate Nearest Neighbor, est une famille d'algorithmes qui identifient rapidement les vecteurs les plus proches d'une requete au sein d'une base de donnees vectorielle volumineuse, en acceptant un leger compromis sur l'exactitude du resultat en echange d'un gain de vitesse considerable par rapport a une recherche exhaustive. Une recherche exacte des plus proches voisins necessite de comparer le vecteur de requete a chacun des vecteurs stockes, une operation dont le cout croit lineairement avec la taille de la base et devient impraticable au-dela de quelques millions d'elements pour des applications a faible latence. Les methodes ANN construisent a l'inverse des structures d'index specialisees, comme les graphes HNSW ou les partitions IVF, qui permettent de ne parcourir qu'une fraction des vecteurs stockes tout en retrouvant, dans la grande majorite des cas, les voisins veritablement les plus proches ou des voisins tres proches de ceux-ci. Cette technologie constitue le fondement technique des bases de donnees vectorielles utilisees dans les architectures RAG, ou elle permet de retrouver en quelques millisecondes les documents semantiquement les plus pertinents parmi des millions de fragments indexes. Le choix des parametres d'un index ANN, comme le niveau de precision souhaite ou la memoire allouee, implique un arbitrage explicite entre vitesse de recherche, consommation de ressources et qualite des resultats retournes.