EUVIMEDEUVIMED entdecken
Crossref

Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search

Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, Raymond Chi-Wing Wong

Proceedings of the ACM on Management of Data · 17.06.2025 · 3 (3) · 1-26

DOI: 10.1145/3725413 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.06.2025. Verfasst von Jianyang Gao und 5 weiteren Autor:innen. Die Arbeit wurde bisher 39-mal zitiert (Crossref) und nennt 86 Literaturangaben. Gefördert von: Ministry of Education - Singapore, HKUST-WeBank Joint Laboratory.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Approximate nearest neighbor (ANN) query in high-dimensional Euclidean space is a key operator in database systems. For this query, quantization is a popular family of methods developed for compressing vectors and reducing memory consumption. Among these methods, a recent algorithm called RaBitQ achieves the state-of-the-art performance and provides an asymptotically optimal theoretical error bound. RaBitQ uses 1 bit per dimension for quantization and compresses vectors with a large compression rate. In this paper, we extend RaBitQ to compress vectors with flexible compression rates - it achieves this by using B bits per dimension for quantization with B = 1, 2, ... It inherits the theoretical guarantees of RaBitQ and achieves the asymptotic optimality in terms of the trade-off between space and error bounds as to be proven in this study. Additionally, we present efficient implementations of the extended RaBitQ, enabling its application to ANN queries to reduce both space and time consumption. Extensive experiments on real-world datasets confirm that our method consistently outperforms the state-of-the-art baselines in both accuracy and efficiency when using the same amount of memory.

Förderung

  • Ministry of Education - Singapore
  • HKUST-WeBank Joint Laboratory

Zitieren

APA

Gao, J., Gou, Y., Xu, Y., Yang, Y., Long, C., & Wong, R. C. (2025). Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data, 3(3), 1-26. https://doi.org/10.1145/3725413

Vancouver

Gao J, Gou Y, Xu Y, Yang Y, Long C, Wong RC. Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data. 2025;3(3):1-26. doi:10.1145/3725413

BibTeX
@article{Gao2025,
  author = {Gao, Jianyang and Gou, Yutong and Xu, Yuexuan and Yang, Yongyi and Long, Cheng and Wong, Raymond Chi-Wing},
  title = {Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2025},
  volume = {3},
  number = {3},
  pages = {1--26},
  doi = {10.1145/3725413}
}
Kostenlos starten →