Un nouveau paradigme pour la indexation vectorielle
Un chercheur a publié une prépublication décrivant une méthode originale d’indexation binaire pour la recherche approximative des plus proches voisins (ANN). Baptisée Barycentric Simplicial Hashing (BSH), elle repose sur la triangulation locale de l’espace vectoriel pour produire des codes compacts à quatre états par triangle. L’auteur affirme que cette approche permet d’atteindre un taux de rappel de 84 à 90 % (Recall@1) en ne consommant que 34 à 38 octets par vecteur, soit environ la moitié des 64 octets nécessaires à la méthode de quantification produit (PQ) utilisée dans la bibliothèque de référence FAISS.
Fonctionnement du hachage simplicial barycentrique
La technique s’applique à un ensemble de vecteurs de base préalablement partitionnés en cellules de Voronoï. À l’intérieur de chaque cellule, le système construit un complexe simplicial k-NN (k plus proches voisins). Pour chaque triangle de ce complexe, la position d’un vecteur est codée sur deux bits : la valeur 0, 1 ou 2 indique la zone du sommet le plus proche, tandis que la valeur 3 désigne la zone du barycentre lorsque celui-ci est le point de référence le plus proche. L’auteur précise que, dans des sous-espaces de dimension 24, l’état « barycentre » est activé pour plus de 51 % des affectations triangle-vecteur, ce qui en fait le discriminateur principal et non un cas rare.
Performances validées sur processeur ARM
Les expériences ont été menées sur des requêtes issues d’une distribution indépendante (sans chevauchement avec les données d’apprentissage) et exécutées sur un processeur ARM Cortex‑X3 à l’aide d’intrinsèques NEON. La méthode BSH a été comparée à l’indexation FAISS IVF-PQ, une référence industrielle. Les résultats montrent un rappel équivalent (85–90 %) pour un gain mémoire d’environ 50 %. L’auteur souligne que les deux méthodes sont indépendantes du matériel et que les validations ont été réalisées sans accélération spécifique.
Implications pour les bases de données vectorielles et les moteurs de recherche
Cette avancée pourrait intéresser les systèmes de recherche d’information à grande échelle, notamment ceux manipulant des plongements (embeddings) de modèles de langage (LLM). En réduisant la mémoire nécessaire au stockage des index, BSH offre une piste pour déployer la recherche de similarité sur des dispositifs contraints, comme les systèmes embarqués ou les téléphones mobiles. Le code source de l’implémentation (langage C++) est accessible via le dépôt Zenodo associé à la prépublication, sous licence Creative Commons Attribution – Pas d’Utilisation Commerciale – Pas de Modification 4.0 International.
Un domaine en pleine effervescence
La recherche en indexation vectorielle connaît un essor soutenu, porté par la multiplication des applications de recherche sémantique et de recommandation. La méthode proposée se distingue par son recours à la topologie simpliciale, un outil mathématique jusqu’ici peu exploité dans ce contexte. L’auteur espère que ce travail ouvrira la voie à de nouvelles architectures de hachage topologique, combinant faible empreinte mémoire et haute précision.
