Product quantization (PQ) is a vector compression technique that partitions a high-dimensional vector into subvectors and quantizes each subspace independently using a learned codebook. Each subspace centroid is assigned an integer code, allowing the original vector to be approximated by a sequence of codebook indices. The quantization error is minimized during training by optimizing codebook centroids via k-means clustering on representative data. At query time, distance computations are accelerated using precomputed lookup tables between the query subvectors and all codebook centroids. Inverted file (IVF) indexes often combine coarse quantization with PQ residual coding to reduce candidate set size before fine-grained distance computation. Optimized product quantization (OPQ) applies a learned rotation to the input space before partitioning to reduce quantization error across subspaces. Asymmetric distance computation (ADC) computes exact query-to-centroid distances while keeping database vectors in their compressed form. Annoy (Approximate Nearest Neighbors Oh Yeah) uses random projection trees instead of quantization, partitioning the vector space recursively by random hyperplanes and searching multiple trees to improve recall. The trade-off between compression ratio, recall, and query latency is central to selecting the right approximate nearest neighbor (ANN) algorithm for large-scale vector databases.
