IVFPQ

IVFPQ, short for Inverted File with Product Quantization, is a scalable indexing technique used for approximate nearest neighbor search in high-dimensional vector spaces. It combines an inverted-file (IVF) structure with product quantization (PQ) to enable fast search over very large datasets while keeping memory usage practical.

In IVF, the vector space is partitioned into a set of coarse centroids using a clustering method such as k-means. Each vector is assigned to its nearest centroid, and the index stores lists of vectors (inverted lists) for every centroid. During a query, only a subset of these lists is examined, reducing the number of distance computations.

PQ further compresses vectors by splitting each vector into several sub-vectors and quantizing each sub-vector with its own small codebook. The result is a compact code for each vector, allowing distance approximations to be computed quickly from short codes rather than full vectors. In IVFPQ, distance estimation between a query and database vectors is performed using the PQ codes within the selected inverted lists, typically via asymmetric distance tables.

Common parameters include the number of coarse centroids (nlist), the number of subquantizers (M), and the bits per sub-quantizer (b). The search pipeline usually involves training the coarse centroids and PQ codebooks, indexing data, and querying by selecting a small number of coarse clusters (nprobe) to probe. IVFPQ offers a balance between recall and speed, trading exactness for scalability.

Applications include large-scale image, text, and multimedia retrieval where billions of vectors must be searched efficiently. While highly effective, performance depends on data distribution and careful tuning of nlist, nprobe, M, and b.