RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search
Preprint
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 outperforms PQ and its variants in terms of accuracy-efficiency trade-off by a clear margin and (2) its empirical performance is well-aligned with our theoretical analysis.Keywords
All Related Versions
This publication has 61 references indexed in Scilit:
- ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithmsInformation Systems, 2020
- LSQ++: Lower Running Time and Higher Recall in Multi-codebook Quantization2018
- High-Dimensional Probability2018
- Approximate nearest neighbor algorithm based on navigable small world graphsInformation Systems, 2014
- Additive Quantization for Extreme Vector Compression2014
- Collaborative Filtering Recommender Systems2007
- A survey of content-based image retrieval with high-level semanticsPattern Recognition, 2007
- Similarity Search The Metric Space Approach2006
- Randomized Algorithms1995
- On universal quantization by randomized uniform/lattice quantizersIEEE Transactions on Information Theory, 1992