IVF-PQ combines inverted-file clustering with product-quantized storage: clustering avoids scanning every vector, while compression reduces the memory footprint of vectors inside the index. section 2.2.2
Its design separates two independent indexing decisions:
- Narrow the search with an inverted file by scanning selected clusters instead of the entire dataset. section 2.2.2
- Store vectors compactly with product quantization, replacing precise values with codebook-based integer identifiers. section 2.2.2
A two-stage search path
The search first takes the highway toward the relevant cluster, then follows local streets to reach nearby vectors. PQ makes those stored vectors smaller, helping large indexes fit in memory. section 2.2.2
Table 2.2 FAISS Indexing Strategies
|
Index Type
|
Best For
|
Key Trade-off
|
Seminal Paper / Origin
|
|
Flat Index (Exact Search)
|
The highest accuracy is required
on smaller datasets (< 100K vectors). Critical for medical/legal
diagnosis.
|
Slow, linear scaling time, making
it unusable for big data.
|
Classical Baseline (Brute-force linear scan)
|
|
IVF (Inverted File)
|
Balance of speed and accuracy for
mid-sized datasets (100K–10M vectors). Enterprise document search.
|
Parameter Sensitivity. Accuracy
depends heavily on the number of clusters (nlist) and probes (nprobe).
|
"Video Google" (Sivic & Zisserman, 2003)
adapted inverted indices for visual vectors.
|
|
HNSW (Hierarchical Navigable Small World)
|
Ultra-fast search is the top
priority, especially for large datasets (> 1M vectors). Real-time
recommendations.
|
High Memory Cost. ~90-95% accuracy
with log-linear search time, but storing the graph structure consumes
significant RAM.
|
Malkov and Yashunin (2016) introduced the hierarchical
graph structure
|
|
Product Quantization (PQ)
|
Low Memory (mobile/embedded).
Often combined with IVF (IVF-PQ) for billion-scale.
|
Lossy. Up to 10x memory reduction
in exchange for a small drop in accuracy.
|
Jégou et al. (2011) defined subspace quantization for
nearest neighbor search.
|
Compare IVF-PQ's clustered-and-compressed design with flat exact search and graph-based HNSW, focusing on speed, accuracy, memory, and tuning trade-offs. section 2.2.2
