Quantization Meets Projection: A Happy Marriage For Approximate K-nearest Neighbor Search

Abstract

Approximate \(k\)-nearest neighbor (AKNN) search is a fundamental problem with wide applications. To reduce memory and accelerate search, vector quantization is widely adopted. However, existing quantization methods either rely on codebooks -- whose query speed is limited by costly table lookups -- or adopt dimension-wise quantization, which maps each vector dimension to a small quantized code for fast search. The latter, however, suffers from a fixed compression ratio because the quantized code length is inherently tied to the original dimensionality. To overcome these limitations, we propose MRQ, a new approach that integrates projection with quantization. The key insight is that, after projection, high-dimensional vectors tend to concentrate most of their information in the leading dimensions. MRQ exploits this property by quantizing only the information-dense projected subspace -- whose size is fully user-tunable -- thereby decoupling the quantized code length from the original dim

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyyang2024quantization

Related papers

• Practical And Asymptotically Optimal Quantization Of High-dimensional Vectors In Euclidean Space For Approximate Nearest Neighbor Search (2024)8.82
• Associative Memories To Accelerate Approximate Nearest Neighbor Search (2016)6.34
• Symphonyqg: Towards Symphonious Integration Of Quantization And Graph For Approximate Nearest Neighbor Search (2024)7.50
• 2-bit Random Projections, Nonlinear Estimators, And Approximate Near Neighbor Search (2016)0.00
• SAQ: Pushing The Limits Of Vector Quantization Through Code Adjustment And Dimension Segmentation (2025)0.00
• Interleaved Composite Quantization For High-dimensional Similarity Search (2019)0.00
• Effective And General Distance Computation For Approximate Nearest Neighbor Search (2024)5.84
• Rabitq: Quantizing High-dimensional Vectors With A Theoretical Error Bound For Approximate Nearest Neighbor Search (2024)12.54