FLAT vs IVF: Comment fonctionne l’index de fichier inversé

Mêmes données, même requête — mais une stratégie de recherche différente. Faites glisser le point de requête, ajustez-le nprobe, puis cliquez sur « Exécuter la recherche » pour voir comment « IVF » ignore la plupart des données.

nprobe2

2 de recherche de grappes « 8 »

Vitesse20ms

Plus la valeur est faible, plus l’animation est rapide

FLAT — Recherche exhaustive

balaye chaque point

Comparaisons

200 / 200

Statut

✓ Terminé

Rappel

100%

IVF — Fichier inversé

recherches nprobe clusters

Comparaisons

33 / 33

Statut

✓ Terminé

Rappel@5

100%

Que se passe-t-il ?

Phase de construction (déjà effectuée) : l’algorithme K-means a partitionné les points de l’ 200 e en 8 grappes. Chaque grappe possède un centroïde (les marques ×).
Étape 1 — évaluation des centroïdes : « IVF » calcule d’abord la distance entre la requête et chaque centroïde. Cela ne représente que 8 comparaisons, quelle que soit la taille de l’ensemble de données.
Étape 2 — sélectionnez les grappes d’ nprobe s les plus proches : celles-ci s’allument. Toutes les autres grappes sont entièrement ignorées.
Étape 3 — balayage des points à l’intérieur des grappes choisies : seulement environ50 des points de l’ 200.

Le compromis : plus nprobe → plus de clusters analysés → un rappel plus élevé mais plus lent. Plus petit nprobe → plus rapide, mais vous risquez de passer à côté de véritables voisins situés dans des grappes non analysées. Essayez de placer nprobe = 1 et de faire glisser la requête près de la limite d’un cluster pour observer la baisse du rappel.

Qu’est-ce qu’un index « IVF » ?

IVF (Inverted File) est un index approximatif du plus proche voisin basé sur le regroupement. Lors de la construction, l’algorithme k-means partitionne tous les vecteurs en nlist grappes, chacune représentée par son centroïde. Au moment de la requête, la recherche compare d’abord la requête aux seuls centroïdes, sélectionne la nprobe et ne parcourt que les vecteurs qu’ils contiennent — en ignorant tout le reste.

Milvus fournit plusieurs variantes d’ IVF s qui font le compromis entre mémoire et précision : IVF_FLAT stocke les vecteurs bruts (précision maximale), IVF_SQ8 compresse chaque dimension à un octet (environ 4 fois moins de mémoire, faible coût de rappel), et IVF_PQ applique une quantification par produit pour une compression bien plus élevée, mais au prix d’un rappel plus important.

nlist s de réglage et nprobe

nlist (temps de construction) : le nombre de grappes k-means. Un point de départ courant est 4 × sqrt(N) pour N vecteurs. Plus il y a de grappes, plus chacune est petite — les balayages sont plus rapides, mais le balayage des centroïdes coûte plus cher et les effets de bord s’amplifient.
nprobe (temps de requête) : nombre de grappes à analyser par requête. Il s’agit du principal paramètre de réglage du rappel et de la latence — c’est précisément ce que contrôle le curseur ci-dessus. Commencez par une valeur d’environ nlist / 16 et augmentez jusqu’à ce que le rappel atteigne votre objectif.
Choix de variante : commencez par « IVF_FLAT ». Passez à « IVF_SQ8 » lorsque la mémoire est insuffisante, puis à « IVF_PQ » uniquement lorsque l’ensemble de données est trop volumineux pour « SQ8 » — et vérifiez le rappel sur vos propres données après chaque étape de réduction.

IVF vs HNSW vs DiskANN

IVF Il se construit rapidement, n’entraîne qu’une faible surcharge mémoire par rapport aux vecteurs et est facile à comprendre — mais pour un même objectif de rappel, l’indexation par « HNSW » répond généralement plus rapidement aux requêtes en mémoire. Choisissez « IVF » lorsque vous reconstruisez souvent les index (la rapidité de construction est importante), lorsque la mémoire est limitée (IVF_SQ8/IVF_PQ), ou lorsque vous souhaitez un comportement de balayage prévisible et ajustable. Optez pour HNSW pour obtenir la latence de requête en mémoire la plus faible, et pour DiskANN lorsque les vecteurs ne tiennent plus du tout dans RAM.

Foire aux questions

Quelle est la différence entre IVF_FLAT, IVF_SQ8 et IVF_PQ?

Ces trois méthodes regroupent les vecteurs de la même manière ; elles diffèrent par la façon dont les vecteurs sont stockés au sein des grappes. « IVF_FLAT » conserve les vecteurs flottants bruts (meilleur rappel). « IVF_SQ8 » quantifie chaque dimension à 8 bits, réduisant ainsi la mémoire d’environ 4 fois avec une légère perte de rappel. « IVF_PQ » remplace les vecteurs par de courts codes de quantification par produit, pour une compression maximale et la plus grande perte de rappel.

Comment choisir entre « nlist » et « nprobe » ?

Une règle empirique courante est la suivante : « nlist = 4 × sqrt(N) » pour N vecteurs ; ajustez ensuite « nprobe » au moment de la requête. Un « nprobe » plus grand analyse davantage de grappes : plus le rappel est élevé, plus la latence est importante. Commencez par environ « nlist/16 » et augmentez jusqu’à ce que le rappel sur un ensemble de requêtes retenu atteigne votre objectif.

Pourquoi « IVF » passe-t-il à côté de certains véritables voisins les plus proches ?

En raison des limites des clusters. Si la requête se trouve près du bord d’un cluster, certains de ses véritables voisins peuvent se situer dans un cluster adjacent qui ne figurait pas parmi les clusters nprobe analysés. Vous pouvez observer ce phénomène dans la visualisation en faisant glisser le point de requête près d’une limite avec nprobe = 1.

Dois-je utiliser IVF ou HNSW?

À rappel égal, la méthode « HNSW » est généralement plus rapide pour la recherche en mémoire, mais elle utilise davantage de mémoire et s’initialise plus lentement. La méthode « IVF » s’initialise rapidement et s’associe bien à la quantification (SQ8/PQ) lorsque la mémoire est limitée. Pour les ensembles de données dépassant largement la limite de RAM, envisagez plutôt la méthode « DiskANN ».

Pour aller plus loin : consultez la documentation «IVF_FLAT » concernant les paramètres d’index, ou consultez «Index Explained» pour obtenir le guide de décision complet.