Rabitq: Quantizing High-dimensional Vectors With A Theoretical Error Bound For Approximate Nearest Neighbor Search
2024 · Jianyang Gao, Cheng Long
Abstract
Searching for approximate nearest neighbors (ANN) in the high-dimensional Euclidean space is a pivotal problem. Recently, with the help of fast SIMD-based implementations, Product Quantization (PQ) and its variants can often efficiently and accurately estimate the distances between the vectors and have achieved great success in the in-memory ANN search. Despite their empirical success, we note that these methods do not have a theoretical error bound and are observed to fail disastrously on some real-world datasets. Motivated by this, we propose a new randomized quantization method named RaBitQ, which quantizes \(D\)-dimensional vectors into \(D\)-bit strings. RaBitQ guarantees a sharp theoretical error bound and provides good empirical accuracy at the same time. In addition, we introduce efficient implementations of RaBitQ, supporting to estimate the distances with bitwise operations or SIMD-based operations. Extensive experiments on real-world datasets confirm that (1) our method outp
Authors
(none)
Tags
Stats
Related papers
- Practical And Asymptotically Optimal Quantization Of High-dimensional Vectors In Euclidean Space For Approximate Nearest Neighbor Search (2024)8.82
- SAQ: Pushing The Limits Of Vector Quantization Through Code Adjustment And Dimension Segmentation (2025)0.00
- Symphonyqg: Towards Symphonious Integration Of Quantization And Graph For Approximate Nearest Neighbor Search (2024)7.50
- Quicker ADC : Unlocking The Hidden Potential Of Product Quantization With SIMD (2018)10.50
- Aisaq: All-in-storage ANNS With Product Quantization For Dram-free Information Retrieval (2024)0.00
- Online Product Quantization (2017)10.61
- Routing-guided Learned Product Quantization For Graph-based Approximate Nearest Neighbor Search (2023)4.52
- Quantization Meets Projection: A Happy Marriage For Approximate K-nearest Neighbor Search (2024)0.00