Vector Compression

Maps continuous floating-point vector components to a discrete set of integer values, typically converting 32-bit floats to 8-bit or 4-bit integers. This linear mapping computes a scale and offset per vector dimension.

• 1-D Compression: Applies quantization independently to each dimension.
• Memory Reduction: Achieves a 4x reduction when converting float32 to int8.
• Error Profile: Introduces uniform quantization error bounded by the step size.
• Use Case: Often the first compression step before applying Product Quantization in a composite index.

Decomposes a high-dimensional vector into M independent subvectors, then quantizes each subvector using a distinct codebook of K centroids learned via k-means clustering. The original vector is stored as a short code of M centroid IDs.

• Memory Footprint: A 128-dim float32 vector (512B) can be compressed to 16 bytes using M=16, K=256.
• Distance Computation: Uses Asymmetric Distance Computation (ADC) where the query is kept in full precision and lookup tables pre-compute distances to all centroids.
• Tradeoff: Compression ratio vs. recall is controlled by the number of subvectors (M) and centroids (K).

An extreme compression method that represents each vector dimension as a single bit based on its sign relative to a threshold (typically zero). A 1024-dim float32 vector collapses to just 128 bytes.

• Hamming Distance: Similarity is computed using the popcount of XOR operations, which is blazingly fast on modern CPUs via SIMD instructions.
• Accuracy Caveat: Works best when the vector distribution is roughly symmetric around the origin; significant information loss occurs otherwise.
• Application: Ideal for first-pass, high-recall candidate generation in a multi-stage retrieval pipeline where a more precise re-ranker follows.

Combines an Inverted File Index (IVF) for coarse spatial partitioning with Product Quantization (PQ) for compressing residual vectors. The IVF step narrows the search to the top-N closest partitions, while PQ compresses the vectors within each partition.

• Two-Level Encoding: Stores a coarse cluster ID and a PQ code for the residual vector.
• Memory Efficiency: Enables billion-scale vector search on machines with limited RAM by storing only compressed residuals.
• Search Process: Query is first assigned to nearest coarse centroids, then ADC is performed only on the PQ-compressed vectors within those selected partitions.

A quantization technique developed by Google that optimizes for Maximum Inner Product Search (MIPS) rather than Euclidean distance. It learns a quantization grid that is anisotropic—stretched and rotated—to preserve inner product scores more accurately than isotropic methods like standard PQ.

• Score-Aware Loss: The codebook is trained to minimize the error in the inner product score, not just the reconstruction error of the vector itself.
• Parallel Beam Search: Coupled with a novel search algorithm that scores multiple quantized candidates in parallel.
• Performance: Achieves superior recall-speed tradeoffs for models where the dot product is the primary similarity metric, such as matrix factorization embeddings.

A recent quantization method that projects vectors onto a randomly rotated basis before applying binary quantization. The random rotation distributes information uniformly across dimensions, mitigating the information loss that plagues naive binary quantization on non-uniform data.

• Theoretical Guarantees: Provides probabilistic bounds on the distance approximation error, offering a mathematically rigorous foundation.
• Fast Encoding: The random rotation can be implemented efficiently using the Fast Hadamard Transform.
• Storage: Achieves compression ratios comparable to binary quantization but with significantly higher recall, making it a strong candidate for disk-based ANN indices like DiskANN.

The foundational compression algorithm that decomposes a high-dimensional vector into M independent subvectors, each quantized using a distinct codebook of K centroids. Instead of storing the original floating-point values, only the index of the nearest centroid is stored, reducing a 128-dimensional float32 vector from 512 bytes to as few as 8 bytes. Distance calculations are accelerated using Asymmetric Distance Computation (ADC), where the query vector remains uncompressed and lookup tables pre-compute distances to all centroids.

A simple compression method that maps continuous floating-point values to a smaller integer representation, typically converting float32 to int8. This achieves a 4:1 compression ratio by dividing the value range into 256 uniform bins. While less aggressive than product quantization, SQ preserves the relative distance ordering between vectors with minimal recall degradation, making it suitable for first-stage retrieval where precision is paramount.

An extreme compression technique that represents each vector dimension as a single bit based on its sign relative to zero. A 1024-dimensional float32 vector collapses to just 128 bytes. Distance computation reduces to hardware-accelerated Hamming distance via the POPCNT instruction. Best suited for high-dimensional vectors where the sign captures sufficient semantic information, but recall drops significantly for nuanced similarity tasks.

A two-level indexing strategy combining Inverted File Index (IVF) for coarse partitioning with Product Quantization for residual compression. The IVF partitions the space into Voronoi cells, and PQ compresses the residual vectors within each cell. This architecture enables billion-scale search on memory-constrained hardware by limiting the search to a few partitions and using compressed distance lookups.

The distortion introduced when mapping a continuous vector to its nearest discrete centroid in a codebook. Measured as the mean squared error between original and reconstructed vectors, this error represents the fundamental tradeoff in compression systems. Higher compression ratios increase quantization error, reducing recall. Techniques like Optimized Product Quantization (OPQ) rotate the space to minimize this error before quantization.

The process of learning representative centroids from a sample of vectors using K-Means clustering. Each subvector space in product quantization requires its own codebook. The codebook size K (typically 256) and the number of subvectors M determine the compression ratio. Training requires a representative sample of the dataset; poorly trained codebooks lead to high quantization error and degraded recall.