ivf

**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.