FR
La compression des graphes HNSW réduit le stockage avec peu de coût en latence
Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search · arXiv:2610.37176
En termes simples
La recherche vectorielle trouve les éléments dont la description chiffrée est proche de celle d’une requête. Un index HNSW (hierarchical navigable small world, ou « petit monde navigable hiérarchique ») stocke aussi des liens entre éléments proches, qui peuvent occuper beaucoup de mémoire.
L’article présente une méthode sans perte pour stocker ces liens HNSW dans moins d’espace, tout en les décodant pendant la recherche. Dans des tests sur quatre jeux de données, la latence est restée proche de celle de la version sans compression pour une précision de recherche identique, tandis que les liens occupaient moins d’espace.
La recherche
Dans un index de recherche vectorielle, les liens du graphe peuvent occuper beaucoup de mémoire, surtout lorsque les vecteurs sont stockés sous une forme compacte.
On ne sait pas encore clairement si ces liens peuvent être compressés tout en permettant à une recherche en ligne de décoder les voisinages visités sans délai important.
Pour les index HNSW (hierarchical navigable small world), les auteurs réordonnent les identifiants des nœuds et encodent sans perte les listes de voisins pour une recherche rapide à la demande.
Dans quatre tests sur des jeux de données variés, les auteurs comparent les graphes compressés avec Stream VByte à Plain, leur version HNSW sans compression. Ils mesurent l’espace occupé par les arêtes et la latence moyenne des requêtes à des niveaux de précision identiques.
Le stockage diminue jusqu’à un facteur de 2.1 sur Sift1M. Sur les quatre jeux de données, la latence égale ou améliore celle de la version sans compression pour trois d’entre eux et n’est que légèrement supérieure sur Sift1M.
Ces résultats étayent un gain de stockage associé à un faible coût mesuré en latence dans ces tests.
Ces résultats étayent un compromis entre stockage et latence pour les configurations HNSW testées, pas pour tous les index de graphes ni toutes les charges de travail.
Les paramètres de recherche ont été ajustés pour atteindre chaque niveau de précision, et l’article n’établit pas qu’ils étaient identiques entre les essais avec et sans compression.
Ce que montrent les preuves
- Le compromis entre stockage et vitesse
Le cadre de compression sans perte des listes d’adjacence HNSW réduit la mémoire utilisée par les liens d’un index HNSW (hierarchical navigable small world, ou « petit monde navigable hiérarchique »). Il répond à un compromis : les liens du graphe peuvent occuper beaucoup de mémoire, surtout lorsque les vecteurs sont compacts, mais la recherche doit décoder les voisinages visités, ce qui peut ajouter de la latence. La question est de savoir si ces liens peuvent prendre moins de place sans ralentir la recherche.
- Pourquoi la copie des listes est écartée
Les auteurs vérifient d’abord si des listes peuvent gagner de la place en faisant référence aux voisins partagés avec d’autres listes. Même un calcul théorique qui ignore le coût des identifiants de référence et autorise des chaînes cycliques sans limite ne donne qu’un gain maximal de 8.8% de l’espace occupé par les arêtes sur eBayProducts7M.
Une méthode pratique économiserait moins et ajouterait du délai lorsque la recherche suit les références ; les auteurs abandonnent donc cette approche et cherchent plutôt à mieux compresser chaque liste.
- Le réordonnancement réduit les écarts
L’étape suivante consiste à réordonner les identifiants des nœuds du graphe pour que les nœuds reliés aient tendance à porter des identifiants proches, puis à stocker les écarts entre identifiants de voisins. Sur eBayProducts7M, l’entropie globale est de 22.62 bits par valeur pour les identifiants d’arêtes d’origine, de 18.52 après encodage ordinaire des écarts et de 14.99 après réordonnancement par EGB.
Cette mesure, calculée sur toutes les valeurs des listes d’adjacence, montre que le réordonnancement facilite la compression des écarts ; elle ne montre pas à elle seule la vitesse de la recherche.
- Mesurer le stockage et la latence
Les auteurs comparent sur quatre jeux de données les graphes compressés avec Stream VByte à Plain, la version sans compression. Accuracy@10 mesure la part des dix plus proches voisins réels trouvés parmi les dix résultats, en moyenne sur les requêtes ; les auteurs comparent la latence moyenne à des niveaux de précision identiques.
Stream VByte réduit jusqu’à un facteur de 2.1 l’espace occupé par les arêtes sur Sift1M, tandis que sa latence reste proche de celle de Plain sur l’ensemble des jeux de données. Ces tests étayent donc un gain de stockage associé à un faible coût mesuré en latence.
- Des résultats en production
L’article présente aussi un résultat distinct obtenu avec le système HNSW en service chez eBay : le stockage du graphe a diminué de 44.3% à rappel identique pour la recherche approximative des plus proches voisins, sans dégradation mesurable de la latence sous les charges de travail réelles.
Cela étaye l’utilité du cadre dans ce système précis. Les tests sur les jeux de données et le résultat en production indiquent une baisse du stockage avec un faible coût mesuré en latence dans les contextes décrits ; les résultats pour d’autres familles d’index de graphes restent à établir.
Détails
- Auteurs de l’article original
- Francesco Benocci, Leonard Dahlmann, Francesco Gargiulo, Tobias Heuer, Silvio Martinico
- Soumis à arXiv
- Licence
- CC BY 4.0