RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search
Proceedings of the ACM on Management of Data · 29.05.2024 · 2 (3) · 1-27
DOI: 10.1145/3654970 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2024. Verfasst von Jianyang Gao und 1 weiteren Autor:innen. Die Arbeit wurde bisher 102-mal zitiert (Crossref) und nennt 96 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-SA 4.0). Gefördert von: Ministry of Education, Singapore.
Abstract (Originalsprache)
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.
Förderung
- Ministry of Education, Singapore
Zitieren
APA
Gao, J., & Long, C. (2024). RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data, 2(3), 1-27. https://doi.org/10.1145/3654970
Vancouver
Gao J, Long C. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data. 2024;2(3):1-27. doi:10.1145/3654970
BibTeX
@article{Gao2024,
author = {Gao, Jianyang and Long, Cheng},
title = {RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search},
journal = {Proceedings of the ACM on Management of Data},
year = {2024},
volume = {2},
number = {3},
pages = {1--27},
doi = {10.1145/3654970}
}
EUVIMED