Inverted File Indexes (IVF)
YouTube search... ...Google search
- K-Nearest Neighbors (KNN)
- Hierarchical Navigable Small World (HNSW)
- AI Solver ... Algorithms ... Administration ... Model Search ... Discriminative vs. Generative ... Optimizer ... Train, Validate, and Test
- Excel ... Documents ... Database; Vector & Relational ... Graph ... LlamaIndex
Inverted File Indexes (IVF) are used in AI for similarity search and nearest neighbor search. IVF is one of the simplest and most basic indexing strategies, and it is commonly used in AI for similarity search and nearest neighbor search. By reducing the search scope, IVF can significantly improve both query speed and throughput. IVF is a partition-based indexing strategy that assigns all database vectors to the partition with the closest centroid. The goal is to map the query vector to a smaller subset of the vector space and then only search that smaller space for approximate nearest neighbors.
Inverted File Product Quantization (IVFPQ)
[1] https://towardsdatascience.com/similarity-search-with-ivfpq-9c6348fd4db3 [2] https://towardsdatascience.com/ivfpq-hnsw-for-billion-scale-similarity-search-89ff2f89d90e [3] https://safjan.com/similarity-search-using-ivfpq/ [4] https://www.pinecone.io/learn/series/faiss/product-quantization/ [5] https://arxiv.org/abs/2210.05521 [6] https://arxiv.org/pdf/2210.05521.pdf
IVF is implemented alongside product quantization (PQ) for a fast and efficient approximate nearest neighbor search. IVFPQ is also commonly referred to as IVFADC in research papers. An inverted file is an index structure that is used to map contents to their locations. IVF reduces the overall search scope by arranging the entire dataset into partitions. All partitions are associated with a centroid, and every vector in the dataset is assigned to a partition that corresponds to its nearest centroid. A two-dimensional Voronoi diagram is used to partition the space into cells, with each cell containing the vectors that are closest to its centroid.
IVFPQ is often used in combination with other techniques to further improve its performance. For example, IVFPQ together with Hierarchical Navigable Small World (HNSW) as the coarse quantizer can deliver an extremely memory-efficient and fast search that is of good accuracy for billion-scale similarity search. IVFPQ is implemented with IndexIVFPQ in Faiss, and the IndexHNSWFlat works as the coarse quantizer for IndexIVFPQ
The popularity of IVFPQ can be attributed to its ability to significantly reduce the retrieval cost, given that the query only needs to access a small fraction of documents guided by IVF. Bi-Phase Enhanced IVFPQ is a recent development that further improves the performance of IVFPQ for time-efficient ad-hoc retrieval.
Faiss library
The `IndexIVF` class in the Faiss library is an implementation of the IVF index. In the inverted file, the quantizer (an `Index` instance) provides a quantization index for each vector to be added. The quantization index maps to a list (aka inverted list or posting list), where the id of the vector is stored. The inverted list object is required only after training. If none is set externally, an `InvertedLists` instance is used automatically.
Faiss is a C++ library developed by Meta Facebook AI Research for efficient similarity search and clustering of dense vectors. It contains algorithms that search in sets of vectors of any size, up to ones that possibly do not fit in RAM. It also contains supporting code for evaluation and parameter tuning. Faiss is written in C++ with complete wrappers for Python. Some of the most useful algorithms are implemented on the GPU.
Faiss provides several similarity search methods that span a wide spectrum of usage trade-offs. It is optimized for memory usage and speed and offers a state-of-the-art GPU implementation for the most relevant indexing methods. Faiss implements a dozen index types that are often compositions of other indices. The optional GPU version has been optimized for billion-scale datasets. Faiss is commonly used in various AI applications, including image and video search, Natural Language Processing (NLP), and recommendation systems. It is also used in research and academic settings for similarity search and clustering of large datasets.
