Week 10 • Day 2Week 10

Day 2:Week 10, Day 2: Partition-Based ANN — Inverted File Index (`IVF`), Voronoi Cells & `nlist`/`nprobe`

Battle-tested daily lesson note • 100% runnable code, interview Q&A, test suite & interactive quiz

Week 10, Day 2: Partition-Based ANN — Inverted File Index (IVF), Voronoi Cells & nlist/nprobe


1. How IVF (IndexIVFFlat) Cuts Search Cost by $20\times\text{–}100\times$

Instead of comparing a query q\mathbf{q} against all NN vectors, Inverted File Index (IVF) partitions the vector space into nlist (KK, typically N\sqrt{N} to $4\sqrt{N})∗∗VoronoiCells∗∗using) **Voronoi Cells** using K$-Means clustering during index construction:

code
┌───────────────────────────────┐ │ nlist = 4 Voronoi Cells │ ├───────────────┬───────────────┤ │ Cell 0 (C0) │ Cell 1 (C1) │ │ • • • │ • ★ q │ <-- Query q lands near C1 & C3 border! ├───────────────┼───────────────┤ │ Cell 2 (C2) │ Cell 3 (C3) │ │ • • │ • • │ └───────────────┴───────────────┘
  1. Build Phase: Learn nlist centroids {μ1,…,μnlist}\{\boldsymbol{\mu}_1, \dots, \boldsymbol{\mu}_{\text{nlist}}\} and assign each document vector vi\mathbf{v}_i to the inverted list (bucket) of its closest centroid.
  2. Search Phase (nprobe):
    • Compare query q\mathbf{q} against the nlist centroids (O(nlist⋅D)O(\text{nlist} \cdot D)).
    • Select the nprobe closest centroids (e.g., nprobe = 8 out of nlist = 1024).
    • Only scan vectors inside those nprobe buckets!
    • Expected Candidate Fraction Scanned: nprobenlist\frac{\text{nprobe}}{\text{nlist}} (e.g., 81024=0.78%\frac{8}{1024} = 0.78\% of the dataset   ⟹  128× speedup!\implies \mathbf{128\times\text{ speedup!}})

2. Why nprobe > 1 is Essential (The Boundary Problem)

What if a query q\mathbf{q} lands right on the boundary between Cell 1 and Cell 3? Its true nearest neighbor might sit just 0.01 units across the border inside Cell 3! If nprobe = 1, IVF only checks Cell 1 and misses the neighbor in Cell 3. Increasing nprobe (1 -> 4 -> 16) smoothly trades extra CPU compute for higher Recall@K!


In Simple English: How IVF Works Like Shopping Mall Aisle Signs

Searching 10 million vectors without an index is checking every single item in a warehouse one by one. IVF (Inverted File Index) groups similar vectors into neighborhoods (Voronoi clusters, say nlist = 1,000 grocery aisles):

  • When a query arrives ("almond milk"), you don't walk down all 1,000 aisles!
  • First check the Aisle Directory (nprobe = 10 nearest aisle signs: "Dairy Alternatives", "Health Foods"...), then scan ONLY the items sitting inside those 10 aisles — jumping 100x faster!
  • Tuning Rule: Higher nprobe = better accuracy (recall), slightly slower search. Lower nprobe = faster search, higher chance of missing borderline items!