Recherche vectorielle, Recherche de similarité, Plus proches voisins approximés, Indexation vectorielle, Base de données vectorielle, Graphe de proximité, K-Plus proches voisins évolutifs

Le manuscrit explore et évalue les méthodes de pointe basées sur les graphes pour la recherche approximative des plus proches voisins (k-NN) dans les applications de recherche vectorielle, essentielles pour la scalabilité des tâches d'apprentissage automatique. La recherche vectorielle facilite la récupération efficace de représentations de données en haute dimension, un aspect fondamental dans diverses applications d'IA telles que les systèmes de recommandation, le traitement du langage naturel et la vision par ordinateur. À mesure que les ensembles de données s'agrandissent et que les modèles gagnent en complexité, il devient crucial de disposer de méthodes de recherche vectorielle évolutives et efficaces pour maintenir les performances et réduire les coûts de calcul. Le travail propose une taxonomie détaillée qui classe les méthodes basées sur les graphes en cinq paradigmes principaux : Sélection de Graines, Propagation de Voisinage, Insertion Incrémentale, Diversification de Voisinage et Diviser-pour-mieux-Régner. Cette classification aide à clarifier les forces et les limites des différentes méthodes, facilitant une compréhension plus profonde de leur impact sur la scalabilité et l'efficacité dans les applications d'apprentissage automatique. Une analyse approfondie de méthodes existantes telles que HNSW, NSG et Vamana identifie les facteurs clés influençant les performances d'indexation et de recherche basées sur les graphes. Les résultats montrent que les méthodes combinant l'Insertion Incrémentale et la Diversification de Voisinage offrent généralement de meilleures performances sur de grands ensembles de données, tandis que celles s'appuyant uniquement sur la Propagation de Voisinage rencontrent des défis en matière de scalabilité. Le manuscrit introduit également ELPIS, une méthode hybride qui combine des stratégies de division pour mieux régner avec l'indexation basée sur les graphes pour améliorer la scalabilité et réduire la surcharge mémoire dans la recherche vectorielle. ELPIS partitionne l'ensemble de données en clusters plus petits à l'aide d'une segmentation arborescente et construit des graphes HNSW au sein de chaque cluster, ce qui permet de surmonter les défis de scalabilité liés au traitement de grands ensembles de données. Les résultats démontrent qu'ELPIS surpasse les méthodes traditionnelles comme HNSW et Vamana en termes de temps d'indexation et de latence de recherche. De plus, des adaptations d'ELPIS traitent des charges de travail à haute latence et à haut débit, cruciales pour les applications en temps réel, en optimisant les compromis entre la taille des clusters et la largeur de faisceau, et en ajustant dynamiquement la taille maximale des feuilles tout en exploitant le multithreading. Le manuscrit présente également OIGAS, une nouvelle approche axée sur l'optimisation du paradigme d'Insertion Incrémentale dans la recherche vectorielle. En adaptant efficacement les exigences pour l'insertion de nouveaux nœuds en fonction de la taille du graphe partiel et en améliorant la connectivité grâce à des stratégies combinées de diversification, OIGAS réalise des réductions significatives du temps d'indexation tout en offrant de meilleures performances de recherche sur divers ensembles de données. En conclusion, le manuscrit fait progresser la compréhension des méthodes de recherche vectorielle basées sur les graphes en fournissant une taxonomie complète et une analyse critique des approches existantes, avec un accent particulier sur la scalabilité en apprentissage automatique. Les méthodes proposées, ELPIS et OIGAS, apportent des solutions innovantes aux défis de scalabilité et d'efficacité inhérents aux grands ensembles de données à haute dimensionnalité, améliorant significativement l'efficacité de l'indexation et de la recherche et soutenant le développement de systèmes d'apprentissage automatique évolutifs.