Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-Based ANN Search
Proceedings of the VLDB Endowment · 2025-07 · 18 (11) · 4337-4349
DOI: 10.14778/3749646.3749697 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 04.09.2025. Verfasst von Ziyang Yue und 8 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 49 Literaturangaben.
Abstract (Originalsprache)
Approximate nearest neighbor (ANN) search is a critical problem in various real-world applications. However, as one of the most promising solutions to ANN search, graph-based indexes often suffer from high memory consumption. Although a few studies attempt to alleviate this issue by storing the index on inexpensive disk storage, they still face challenges such as insufficient data locality and low efficiency when optimizing the graph layout on disk. Therefore, we propose MARGO, a monotonic path-aware graph layout optimization method for disk-based ANN search. First, we present the essence of graph layout optimization in disk-based ANN search, and design a monotonic path-aware objective function that weighs the edges based on their importance in monotonic paths, supported by rigorous theoretical analysis. Second, we propose a greedy algorithm that prioritizes high-weight edges to accommodate more monotonic paths. To enhance efficiency, MARGO introduces a two stage decoupling method that processes intra-cluster edges in parallel first, followed by inter-cluster edges. Third, we develop a weight computation strategy that computes edge weights on-the-fly during index construction with almost no additional overhead. A comprehensive experimental study demonstrates that MARGO improves search efficiency by up to 26.6% while maintaining the same recall, and accelerates the graph layout optimization by up to 5.5×.
Zitieren
APA
Yue, Z., Zheng, B., Xu, L., Xu, K., Zhang, S., Du, Y., Gao, Y., Zhou, X., & Jensen, C. S. (2025). Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-Based ANN Search. Proceedings of the VLDB Endowment, 18(11), 4337-4349. https://doi.org/10.14778/3749646.3749697
Vancouver
Yue Z, Zheng B, Xu L, Xu K, Zhang S, Du Y, et al. Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-Based ANN Search. Proceedings of the VLDB Endowment. 2025;18(11):4337-4349. doi:10.14778/3749646.3749697
BibTeX
@article{Yue2025,
author = {Yue, Ziyang and Zheng, Bolong and Xu, Ling and Xu, Kanru and Zhang, Shuhao and Du, Yajuan and Gao, Yunjun and Zhou, Xiaofang and Jensen, Christian S.},
title = {Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-Based ANN Search},
journal = {Proceedings of the VLDB Endowment},
year = {2025},
volume = {18},
number = {11},
pages = {4337--4349},
doi = {10.14778/3749646.3749697}
}
EUVIMED