Inverted File Index (IVF)

Let’s explore IVF in depth, using our toy dataset to illustrate how it reduces search space while maintaining accuracy.

1. The Problem: Why IVF?

Imagine you’re searching for a book in a library with 1 million books. Brute-force would mean scanning every shelf. Instead, you:

1. Categorize books into sections (e.g., "Sci-Fi," "History").
2. Search only relevant sections for your query.

IVF does this for vectors. Let’s formalize it.

2. IVF Workflow

Step 1: Clustering with K-means

Objective: Partition the dataset into $K$ clusters (sections) to avoid scanning all vectors.

1. K-means Formulation:
   Given $n$ vectors $X=\{{\mathbf{x}}_1,...,{\mathbf{x}}_n\}\subset {\mathbb{R}}^d$, find $K$ centroids $\{{\mu }_1,...,{\mu }_K\}$ that minimize:

   $$\underset{\{{\mu }_k\}}{min}\sum _{k=1}^K\sum _{\mathbf{x}\in C_k}\parallel \mathbf{x}-{\mu }_k{\parallel }^2$$

   where $C_k$ is the $k$-th cluster.

2. Example:
   For our toy dataset ($K=3$):

   • Cluster 1 (Red): $[1.1,0.9]$, $[1.0,1.2]$ → Centroid ${\mu }_1=[1.05,1.05]$.
   • Cluster 2 (Green): $[5.2,5.0]$, $[5.1,4.8]$, $[5.3,5.1]$ → Centroid ${\mu }_2=[5.2,4.97]$.
   • Cluster 3 (Blue): $[9.0,1.0]$, $[9.5,0.8]$, $[8.9,1.2]$ → Centroid ${\mu }_3=[9.13,1.0]$.

Step 2: Building Inverted Lists

For each centroid ${\mu }_k$, maintain a list of vectors in its cluster:

• Cluster 1: $[0,1]$ (indices of vectors $[1.1,0.9]$ and $[1.0,1.2]$).
• Cluster 2: $[2,3,4]$ (indices of green vectors).
• Cluster 3: $[5,6,7]$ (indices of blue vectors).

Step 3: Querying with IVF

For a query $\mathbf{q}=[5.4,5.2]$:

1. Find Nearest Centroids:
   Compute distances to all $K$ centroids:$$\parallel \mathbf{q}-{\mu }_1{\parallel }^2=18.2,\parallel \mathbf{q}-{\mu }_2{\parallel }^2=0.07,\parallel \mathbf{q}-{\mu }_3{\parallel }^2=16.5$$
2. Probe Clusters:
   Select the closest $n_{\text{probe}}=1$ cluster (Cluster 2).
3. Search Only in Cluster 2:
   Compare $\mathbf{q}$ to vectors $\{[5.2,5.0],[5.1,4.8],[5.3,5.1]\}$.

3. Key Parameters & Trade-offs

Mathematical Trade-off

The probability of missing the true nearest neighbor is bounded by:

• Example: For $K=256$, $n_{\text{probe}}=20$:$$P_{\text{miss}}\propto \exp (-\frac{20}{256})\approx 0.92$$This means a ~8% chance of missing the true neighbor, but search speed improves by 12.8x (since $\frac{K}{n_{\text{probe}}}=\frac{256}{20}=12.8$).

4. Example Walkthrough

1. Clustering:

   • Input: 8 vectors in ${\mathbb{R}}^2$.
   • Output: 3 clusters with centroids ${\mu }_1$, ${\mu }_2$, ${\mu }_3$.

2. Query $\mathbf{q}=[5.4,5.2]$:

   • Step 1: Compare $\mathbf{q}$ to centroids.
   • Step 2: Narrow search to Cluster 2 (green).
   • Step 3: Compute distances to 3 vectors in Cluster 2 instead of 8.

3. Result:

   • Brute-force: 8 distance calculations.
   • IVF: 3 centroid distances + 3 vector distances = 6 calculations (25% faster).

5. Why This Matters for Real-World Data

For a dataset with 1B vectors and $K=256$:

• Brute-force: $1B\times 1536=1.536\times {10}^{12}$ operations.
• IVF: $\frac{20}{256}\times 1B\times 1536=1.2\times {10}^{11}$ operations (12.8x faster).

6. Summary

Next, we’ll explore Product Quantization (PQ)—the second pillar of IVF-PQ!