IVF (Inverted File Index)

Overview IVF (Inverted File Index) is one of the most common indexing algorithms used in Vector Databases to speed up similarity search. It allows for "Approximate Nearest Neighbor" (ANN) search, trading a tiny bit of accuracy for massive speed gains.

How it works

1. Training (Clustering)

• Look at all your vectors (e.g., 1 million points).
• Use K-Means clustering to find $N$ "centroids" (center points).
• Partition the space into "Voronoi cells" around these centroids.

2. Indexing

• Assign every vector to its nearest centroid.
• Store them in an "inverted list" bucket for that centroid.

3. Usage (Search)

• When a query vector comes in, find the closest centroid.
• ONLY search the vectors inside that centroid's bucket (and maybe a few neighbors: nprobe).
• Result: You search 1% of the data instead of 100%.

Trade-offs

• nprobe: How many buckets to check.
• Low nprobe: Fast, but might miss the answer.
• High nprobe: Slower, higher accuracy (Recall).
• Training time: Building the index takes time (running K-Means).

IVF is often combined with Product Quantization (IVF-PQ) for maximum speed and compression in tools like FAISS and Milvus.