Présentation M1 · Recherche

Recherche Approchée de Plus Proches Voisins (ANNS) en Haute Dimension

Synthèse de deux articles sur les structures d'index et la réduction de dimensionnalité pour l'ANNS moderne.

Article 1 · IEEE Data Eng. Bulletin 2023

Graph- and Tree-based Indexes for High-dimensional Vector Similarity Search

Z. Wang, P. Wang, T. Palpanas, W. Wang

Article 2 · 2024

Dimensionality-Reduction Techniques for Approximate Nearest Neighbor Search: A Survey

Z. Wang, H. Xiong, Q. Wang et al.

10 minutes 2 Articles Haute Dimension

Contexte

Qu'est-ce que l'ANNS et pourquoi c'est critique ?

Trouver les éléments les plus similaires à une requête dans un grand ensemble — avec de légères approximations pour gagner en vitesse.

Recall k@k = |A ∩ G| / k → cible >95%

L'essor des embeddings

↑

Qwen2 (Alibaba) : 3 584 dimensions · SFR (Salesforce) : 4 096 dimensions

!

Le coût de calcul des distances croît linéairement avec la dimensionnalité — c'est le fléau de la dimension

Applications concrètes

✓

RAG — Retrieval-Augmented Generation pour augmenter les LLMs

✓

Recherche sémantique d'images et de documents

✓

Recommandation — Netflix, Spotify, e-commerce

✓

Bases vectorielles — Milvus, Pinecone, pgvector

Enjeu

Des milliards de vecteurs, des milliers de dimensions, des millisecondes pour répondre.

Contexte

Le goulot d'étranglement : calcul de distances

Dans HNSW (l'index de référence), le calcul des distances représente

60–90%

du temps total de traitement d'une requête

Complexité L2 : O(D) — D = dimensionnalité

C'est pourquoi ces deux articles attaquent le problème sous deux angles complémentaires.

Article 1 — Structurer les données

Optimiser les structures d'index (graphes, arbres) pour réduire le nombre de distances calculées.

Article 2 — Réduire la dimension

Réduire D pour accélérer chaque calcul individuel — approche orthogonale à n'importe quel index.

Article 1 — Index graphes

Graphes : évolution K-Graph → HNSW

Chaque vecteur = un sommet. Les arêtes connectent des vecteurs proches. La recherche gloutonne navigue le graphe en se rapprochant de la requête.

K-Graph Hubs

Chaque nœud → ses K plus proches voisins. Les hubs (k-occurrence élevée) s'interconnectent entre eux (>50% des liens) → la recherche se retrouve piégée dans ces zones.

NSW Connexions longue distance

Insertion aléatoire séquentielle → crée des liens longue distance qui brisent les clusters de hubs. 32% d'étapes en moins vs K-Graph.

HNSW Référence

Structure hiérarchique + degré borné (2M) + règle d'élagage RNG. Utilisé dans FAISS, hnswlib, Milvus.

Vamana / HVS / NSG

Relaxation de RNG, meilleurs points d'entrée (HVS/LSH-APG → 3× plus rapide), garantie d'accessibilité globale (NSG).

Clé de HNSW — Règle RNG

Supprime les arêtes redondantes → libère des slots pour des connexions longue distance. Résultat : seulement ~30% des arêtes de K-Graph conservées, corrélation hub/connexion divisée par 3.

Article 1 — Ablation & Arbres

HNSW : résultats mesurés & index à base d'arbres

Effets mesurés de la règle RNG

▸

~30% des arêtes de K-Graph conservées — le reste = connexions longue distance

▸

Asymétrie de la distribution des degrés réduite de moitié

▸

Corrélation in-degree / k-occurrence : <0.3 (contre 1.0 dans K-Graph)

!

La hiérarchie HNSW est quasi inutile en haute dimension : HNSW₀ (couche basse) donne les mêmes performances

HVS / LSH-APG : index auxiliaire pour de meilleurs points d'entrée → jusqu'à 3× plus rapide que HNSW.

Index à base d'arbres

Partitionnement hiérarchique de l'espace. Traversée racine → feuilles. 3 familles :

①

iSAX : symbolisation hiérarchique + borne inférieure sur la distance → élagage sans faux négatifs Dumpy

②

EAPCA : segmentation dynamique + moyenne/écart-type → bornes plus serrées ELPIS

③

Ordonnée : courbes remplissantes (Z-order, Hilbert) + B-tree HD-Index

Combinaison optimale

ELPIS : arbre pour partitionner + graphe dans chaque feuille → 3–8× moins de temps d'indexation, −40% de mémoire.

Article 1 — Comparaison

Graphes vs Arbres

Critère	Graphes (HNSW…)	Arbres (iSAX, ELPIS…)
Élagage garanti	Non	Oui (bornes inférieures)
Localité des données	Non	Oui (données groupées)
Index sur disque	Difficile	Naturel
Scalabilité / Distribué	Limitée, peu exploré	Excellente (Odyssey, TARDIS)
Performance en mémoire	★★★★★ Meilleure	★★★☆☆ Correcte

Conclusion Article 1

Graphes pour la précision en mémoire, arbres pour la scalabilité et le disque. Les combinaisons (ELPIS, SPANN) donnent le meilleur des deux. Défi ouvert : performances variant jusqu'à 90× selon les datasets.

Article 2 — Réduction de dimensionnalité

Deux frameworks, six techniques

① IN-PLACE

Transforme le dataset avant l'index. Calcul de distance par dimension avec terminaison anticipée dès que la distance partielle dépasse le seuil.

PCA DWT ADSampling

② OUT-OF-PLACE

Index sur données brutes + structure auxiliaire réduite. On estime d'abord, on calcule exactement seulement si nécessaire.

PM-LSH OPQ SEANet*

Technique	Framework	Garantie	Coût mémoire	Point fort
PCA	In-Place	Exacte	O(D²)	Le plus précis
DWT	In-Place	Exacte	0 !	Le plus léger (O(D), sans matrice)
ADSampling	In-Place	Probabiliste	O(D²)	Simple (Johnson-Lindenstrauss)
PM-LSH	Out-of-Place	Probabiliste	Nd+Dd	Ultra-basse dimension (ex: 16D)
OPQ	Out-of-Place	Aucune	Nm+DKs+D²	Estimation la plus rapide — très robuste
SEANet*	Out-of-Place	Aucune	O(X)	Deep learning — potentiel sur H&M

Article 2 — Résultats

Résultats expérimentaux (Recall 98%)

Speedup sans SIMD

Trevi (4096D)

6.3× — DWT

H&M (2048D)

2.1× — ADS

GIST (960D)

2.0× — DWT

MNIST (784D)

1.6× — OPQ

Deep (96D)

1.1×

Seuil critique

Les gains deviennent spectaculaires (>2×) au-delà de ~700 dimensions. En dessous, les gains sont marginaux — encore plus avec les instructions SIMD (AVX) déjà présentes dans FAISS/hnswlib.

Avec SIMD (AVX)

▸

Trevi : 2.2× (réduit car SIMD accélère déjà le calcul brut)

▸

GIST : 1.7×

▸

H&M : 1.2× — aucune amélioration sous 800D

▸

OPQ profite mieux de SIMD que PCA grâce à la quantification

Article 2 — Conclusions

Conclusions et axes de recherche ouverts

Résultat central

Aucune technique ne domine universellement. Le choix optimal dépend du dataset (dimension, densité, difficulté).

Recommandations pratiques

▸

D > 2000 : DWT ou PCA (gains jusqu'à ×6)

▸

D ≈ 700–2000 : ADSampling ou OPQ

▸

D modérée : OPQ (robuste, estimation la plus rapide)

▸

D < 300 : gains négligeables, surtout avec SIMD

Quatre axes de recherche

① Quantification avec garanties

Combiner la vitesse de PQ avec les garanties de LSH ou de la transformation in-place.

② Réseaux de neurones profonds

SEANet* montre un potentiel fort. Architecture, fonction de perte, entraînement — vaste espace de conception.

③ Sélection adaptative automatique

Choisir automatiquement la meilleure technique selon les caractéristiques du dataset.

④ Compression de stockage

Réduction de dimension + quantification scalaire pour comprimer le stockage dans les bases vectorielles.

Synthèse

Ce qu'il faut retenir

Article 1 — Index

Comment structurer les données ?
Graphes (HNSW) pour la précision en mémoire, arbres pour la scalabilité, combinaisons (ELPIS) pour le meilleur des deux.

Article 2 — Réduction de dim.

Comment accélérer chaque calcul ?
Approche orthogonale à n'importe quel index. Gains spectaculaires au-delà de 700D — jusqu'à 6× sans SIMD.

01

Le calcul de distance est le goulot : 60–90% du temps de requête dans HNSW.

02

La règle RNG est la clé du succès de HNSW — elle brise les clusters de hubs en libérant des connexions longue distance.

03

Graphes et arbres sont complémentaires — les combiner (ELPIS, SPANN) donne les meilleurs résultats sur grands datasets.

04

La réduction de dimensionnalité est orthogonale à l'index : elle améliore n'importe quel algorithme ANNS existant.

05

Aucune technique ne domine universellement : la sélection adaptative et les garanties sur la quantification restent des problèmes ouverts majeurs.