RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search
Top Cited Papers
Open Access
- 29 May 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (3) , 1-27
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
Funding Information
- Ministry of Education, Singapore (MOE-T2EP20220-0011)
- Ministry of Education, Singapore (RG77/21)
- Ministry of Education, Singapore (MOE-T2EP20221-0013)
This publication has 69 references indexed in Scilit:
- DB-LSH: Locality-Sensitive Hashing with Query-based Dynamic Bucketing2022
- Fast Adaptive Similarity Search through Variance-Aware Quantization2022
- ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithmsInformation Systems, 2020
- High-Dimensional Probability2018
- Link and Code: Fast Indexing with Graphs and Compact Regression Codes2018
- Optimality of the Johnson-Lindenstrauss Lemma2017
- Additive Quantization for Extreme Vector Compression2014
- Optimized Product Quantization for Approximate Nearest Neighbor Search2013
- A survey of content-based image retrieval with high-level semanticsPattern Recognition, 2007
- On universal quantization by randomized uniform/lattice quantizersIEEE Transactions on Information Theory, 1992