Indexation vectorielle
Structures exactes
Kd-Tree (k-dimensional tree)
Un Kd-Tree est une structure d’arbre binaire qui permet d’organiser des points dans un espace de dimension k.
- Chaque nœud de l’arbre représente un point (vecteur).
- À chaque niveau de l’arbre, on découpe l’espace selon une dimension spécifique.
Ainsi, l’espace est récursivement partitionné en hyperplans (droites en 2D, plans en 3D, hyperplans en kD).
- On choisit une dimension de séparation (ex. la dimension x).
- On prend le point médian selon cette dimension → il devient le nœud racine.
- Les points avec des coordonnées inférieures vont dans le sous-arbre gauche, les autres dans le sous-arbre droit.
- On recommence récursivement en changeant la dimension (ex. au niveau suivant on coupe selon y, puis z, ... puis de nouveau x).
Chaque étape partitionne l’espace en rectangles de plus en plus petits.
Ball-Tree
Au lieu de couper par des hyperplans, on coupe par des hypersphères → mieux adapté pour distances euclidiennes.
Le Kd-Tree est une structure d’indexation exacte, très efficace pour la recherche de voisins proches en faible dimension. Mais il ne passe pas à l’échelle en haute dimension, ce qui a conduit au développement des méthodes approximatives.
Structures approximatives
Locality Sensitive Hashing (LSH)
L’idée est de construire des fonctions de hachage probabilistes qui envoient :
les vecteurs similaires → dans le même seau (bucket) avec forte probabilité,
les vecteurs différents → dans des seaux distincts avec forte probabilité.
Contrairement à un hachage classique (qui disperse les données), ici le hachage est conçu pour conserver la notion de proximité.
Inverted File (IVF)
Appliquer k-means pour créer C clusters.
Assigner chaque vecteur au centroïde le plus proche.
Dans chaque cluster, stocker uniquement les résidus (différence vecteur – centroïde).
Utiliser Product Quantization (PQ) pour encoder ces résidus en codes compacts (ex. 8 bits par sous-espace).
Hierarchical Navigable Small World (HNSW)
Basé sur les graphes de proximité : chaque vecteur est un nœud relié à ses voisins proches.
On construit un graphe navigable qui permet de trouver les plus proches voisins sans explorer toute la base.
Inspiré des graphes "small-world" : on peut atteindre rapidement un point du graphe en peu de sauts.
Le choix d'un index est un compromis
- Exact = lent mais précis.
- Approximatif = rapide mais avec une petite perte de précision.