Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-27
DOI: 10.1145/3802045 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Weijian Chen und 5 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 68 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
On-disk graph-based approximate nearest neighbor search (ANNS) is essential for large-scale, high-dimensional vector retrieval, yet its performance is widely recognized to be limited by the prohibitive I/O costs. Interestingly, we observed that the performance of on-disk graph-based index systems is compute-bound, not I/O-bound, with the rising of the vector data dimensionality (e.g., hundreds or thousands). This insight uncovers a significant optimization opportunity: existing on-disk graph-based index systems universally target I/O reduction and largely overlook computational overhead, which leaves a substantial performance improvement space. In this work, we propose Laser, an efficient on-disk graph-based index system for large-scale high-dimensional vector similarity search. In particular, we first conduct performance analysis on existing on-disk graph-based index systems via the adapted roofline model, then we devise a novel on-disk data layout in Laser to effectively alleviate the compute-bound, which is revealed by the above roofline model analysis, by exploiting SIMD instructions on modern CPUs. We next design a suite of optimization techniques (e.g., degree-based node cache, cluster-based entry point selection, and early dispatch strategy) to further improve the performance of Laser. We last conduct extensive experimental studies on a wide range of large-scale high-dimensional vector datasets to verify the superiority of Laser. Specifically, Laser not only surpasses existing on-disk graph-based index systems but also matches or even exceeds the performance of in-memory index systems.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Chen, W., Liu, H., Deng, Y., Xiang, L., Huang, L., & Tang, B. (2026). Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search. Proceedings of the ACM on Management of Data, 4(3), 1-27. https://doi.org/10.1145/3802045
Vancouver
Chen W, Liu H, Deng Y, Xiang L, Huang L, Tang B. Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search. Proceedings of the ACM on Management of Data. 2026;4(3):1-27. doi:10.1145/3802045
BibTeX
@article{Chen2026,
author = {Chen, Weijian and Liu, Haotian and Deng, Yangshen and Xiang, Long and Huang, Liang and Tang, Bo},
title = {Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--27},
doi = {10.1145/3802045}
}
EUVIMED