FLAT vs IVF: Come funziona l’indice a file invertito

Stessi dati, stessa query — ma una strategia di ricerca diversa. Trascinare il punto di query, regolare nprobee premi “Esegui ricerca ” per vedere come “ IVF ” salti la maggior parte dei dati.

nprobe2

2 e di ricerca di cluster 8

Velocità20ms

Più basso = animazione più veloce

FLAT — Ricerca esaustiva

esamina ogni punto

Confronti

200 / 200

Stato

✓ Fatto

Recall

100%

IVF — File invertito

ricerche su cluster nprobe

Confronti

33 / 33

Stato

✓ Fatto

Recall@5

100%

Cosa sta succedendo?

Fase di costruzione (già completata): l’algoritmo K-means ha suddiviso i punti dell’ 200 e in 8 cluster. Ogni cluster ha un centroide (i segni ×).
Fase 1 — valutazione dei centroidi: IVF calcola innanzitutto la distanza dalla query a ciascun centroide. Si tratta di sole 8 i confronti, indipendentemente dalle dimensioni del set di dati.
Fase 2 — selezionare i cluster più vicini all’ nprobe: questi si illuminano. Tutti gli altri cluster vengono saltati completamente.
Fase 3 — scansione dei punti all’interno dei cluster scelti: solo circa50 dei punti 200.

Il compromesso: più nprobe → più cluster analizzati → recall più elevato ma maggiore lentezza. Più piccolo nprobe → più veloce, ma si potrebbero tralasciare i veri vicini che si trovano in cluster non analizzati. Provare a impostare nprobe = 1 e trascinare la query vicino al confine di un cluster per osservare il calo del recall.

Che cos’è un indice “ IVF ”?

IVF (Inverted File) è un indice approssimativo del vicino più prossimo basato sul clustering. In fase di costruzione, l’algoritmo k-means suddivide tutti i vettori in nlist cluster, ciascuno rappresentato dal proprio centroide. Al momento della query, la ricerca confronta innanzitutto la query solo con i centroidi, seleziona i nprobe e scansiona solo i vettori al loro interno, tralasciando tutto il resto.)

Milvus fornisce diverse varianti di " IVF " che sacrificano la memoria a favore della precisione: IVF_FLAT memorizza i vettori grezzi (massima precisione), IVF_SQ8 comprime ogni dimensione in un byte (~4 volte meno memoria, con un piccolo costo in termini di recall), e IVF_PQ applica la quantizzazione del prodotto per una compressione molto più elevata con un costo di recall maggiore.

Ottimizzazione nlist e nprobe

nlist (tempo di costruzione): il numero di cluster k-means. Un punto di partenza comune è 4 × sqrt(N) per N vettori. Un numero maggiore di cluster implica che ciascuno sia più piccolo — scansioni più veloci, ma la scansione dei centriidi costa di più e gli effetti di confine aumentano.
nprobe (tempo di query): quanti cluster scansionare per ogni query. Questa è la principale leva di regolazione tra recall e latenza — esattamente ciò che controlla il cursore sopra. Inizia da circa nlist / 16 e aumentare fino a quando il recall non raggiunge l’obiettivo desiderato.
Scelta delle varianti: iniziare con IVF_FLAT. Passare a IVF_SQ8 quando la memoria è limitata e a IVF_PQ solo quando il set di dati è troppo grande per SQ8 — e verificare il recall sui propri dati dopo ogni passaggio a una variante con meno risorse.

IVF vs HNSW vs DiskANN

IVF si costruisce rapidamente, ha un overhead di memoria ridotto rispetto ai vettori ed è facile da comprendere — ma a parità di obiettivo di recall, HNSW di solito risponde alle query più velocemente in memoria. Scegli IVF quando ricostruisci spesso gli indici (la velocità di costruzione è importante), quando la memoria è limitata (IVF_SQ8/IVF_PQ), o quando desideri un comportamento di scansione prevedibile e ottimizzabile. Scegliere HNSW per la minima latenza delle query in memoria e DiskANN quando i vettori non rientrano più affatto in RAM.

Domande frequenti

Qual è la differenza tra IVF_FLAT, IVF_SQ8 e IVF_PQ?

Tutti e tre raggruppano i vettori allo stesso modo; differiscono nel modo in cui i vettori vengono memorizzati all’interno dei cluster. « IVF_FLAT » conserva i vettori float grezzi (miglior recall). « IVF_SQ8 » quantizza ogni dimensione a 8 bit, riducendo la memoria di circa 4 volte con una piccola perdita di recall. « IVF_PQ » sostituisce i vettori con brevi codici di quantizzazione del prodotto per ottenere la massima compressione e la maggiore perdita di recall.

Come devo scegliere tra “ nlist ” e “ nprobe ”?

Una regola empirica comune è che nlist = 4 × sqrt(N) per N vettori; quindi ottimizzare nprobe al momento della query. Un valore maggiore di nprobe scansiona più cluster: maggiore recall, maggiore latenza. Iniziare con circa nlist/16 e aumentare fino a quando il recall su un insieme di query tenuto da parte non soddisfa l’obiettivo.

Perché l’algoritmo “ IVF ” tralascia alcuni veri vicini più prossimi?

A causa dei confini dei cluster. Se la query si trova vicino al bordo di un cluster, alcuni dei suoi veri vicini potrebbero trovarsi in un cluster adiacente che non era tra i cluster nprobe scansionati. È possibile osservarlo nella visualizzazione trascinando il punto di query vicino a un confine con nprobe = 1.

Devo usare IVF o HNSW?

A parità di recall, l’algoritmo « HNSW » è solitamente più veloce per la ricerca in memoria, ma utilizza più memoria e richiede più tempo per essere compilato. L’algoritmo « IVF » si compila rapidamente e si abbina bene alla quantizzazione (SQ8/PQ) quando la memoria è limitata. Per i set di dati che superano completamente i limiti di RAM, considerare invece DiskANN.

Approfondisci: leggi la documentazione "IVF_FLAT " per i parametri di indicizzazione, oppure consulta " Index Explained " per la guida completa alle decisioni.