EUVIMEDEUVIMED entdecken
Crossref

Accelerating Graph Indexing for ANNS on Modern CPUs

Mengzhao Wang, Haotian Wu, Xiangyu Ke, Yunjun Gao, Yifan Zhu, Wenchao Zhou

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

DOI: 10.1145/3725260 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.06.2025. Verfasst von Mengzhao Wang und 5 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 128 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In high-dimensional vector spaces, Approximate Nearest Neighbor Search (ANNS) is a key component in database and artificial intelligence infrastructures. Graph-based ANNS methods, particularly HNSW, have emerged as leading solutions, offering an impressive trade-off between search efficiency and accuracy. Many vector databases utilize graph indexes as their core algorithms, benefiting from various optimizations to enhance search performance. However, the high indexing time associated with graph algorithms poses a significant challenge, especially given the increasing volume of data, query processing complexity, and dynamic index maintenance demand. This has rendered indexing time a critical performance metric for users. In this paper, we comprehensively analyze the underlying causes of the low graph indexing efficiency on modern CPUs, identifying that distance computation dominates indexing time, primarily due to high memory access latency and suboptimal arithmetic operation efficiency. We demonstrate that distance comparisons during index construction can be effectively performed using compact vector codes at an appropriate compression error. Drawing from insights gained through integrating existing compact coding methods in the graph indexing process, we propose a novel compact coding strategy, named Flash, designed explicitly for graph indexing and optimized for modern CPU architectures. By minimizing random memory accesses and maximizing the utilization of SIMD (Single Instruction, Multiple Data) instructions, Flash significantly enhances cache hit rates and arithmetic operations. Extensive experiments conducted on eight real-world datasets, ranging from ten million to one billion vectors, exhibit that Flash achieves a speedup of 10.4× to 22.9× in index construction efficiency, while maintaining or improving search performance.

Zitieren

APA

Wang, M., Wu, H., Ke, X., Gao, Y., Zhu, Y., & Zhou, W. (2025). Accelerating Graph Indexing for ANNS on Modern CPUs. Proceedings of the ACM on Management of Data, 3(3), 1-29. https://doi.org/10.1145/3725260

Vancouver

Wang M, Wu H, Ke X, Gao Y, Zhu Y, Zhou W. Accelerating Graph Indexing for ANNS on Modern CPUs. Proceedings of the ACM on Management of Data. 2025;3(3):1-29. doi:10.1145/3725260

BibTeX
@article{Wang2025,
  author = {Wang, Mengzhao and Wu, Haotian and Ke, Xiangyu and Gao, Yunjun and Zhu, Yifan and Zhou, Wenchao},
  title = {Accelerating Graph Indexing for ANNS on Modern CPUs},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2025},
  volume = {3},
  number = {3},
  pages = {1--29},
  doi = {10.1145/3725260}
}
Kostenlos starten →