{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T04:19:55Z","timestamp":1789186795029,"version":"build-2803163510"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>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\u00d7.<\/jats:p>","DOI":"10.14778\/3749646.3749697","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4337-4349","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-Based ANN Search"],"prefix":"10.14778","volume":"18","author":[{"given":"Ziyang","family":"Yue","sequence":"first","affiliation":[{"name":"Huazhong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bolong","family":"Zheng","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ling","family":"Xu","sequence":"additional","affiliation":[{"name":"Shuyi Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kanru","family":"Xu","sequence":"additional","affiliation":[{"name":"Shuyi Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuhao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yajuan","family":"Du","sequence":"additional","affiliation":[{"name":"Wuhan University of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"HKUST"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204034"},{"key":"e_1_2_1_2_1","volume-title":"Mount","author":"Arya Sunil","year":"1993","unstructured":"Sunil Arya and David M. Mount. 1993. Approximate Nearest Neighbor Queries in Fixed Dimensions. In SODA. 271\u2013280."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Akari Asai Sewon Min Zexuan Zhong and Danqi Chen. 2023. Retrieval-based Language Models and Applications. In ACL. 41\u201346.","DOI":"10.18653\/v1\/2023.acl-tutorials.6"},{"key":"e_1_2_1_4_1","volume-title":"ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst. 87","author":"Aum\u00fcller Martin","year":"2020","unstructured":"Martin Aum\u00fcller, Erik Bernhardsson, and Alexander John Faithfull. 2020. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst. 87 (2020)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_6_1","unstructured":"Tom B. Brown Benjamin Mann Nick Ryder et al. 2020. Language Models are Few-Shot Learners. In NeurIPS."},{"key":"e_1_2_1_7_1","first-page":"2735","article-title":"RoarGraph","volume":"17","author":"Chen Meng","year":"2024","unstructured":"Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X. Sean Wang. 2024. RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search. PVLDB. 17, 11 (2024), 2735\u20132749.","journal-title":"PVLDB."},{"key":"e_1_2_1_8_1","volume-title":"SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In NeurIPS. 5199\u20135212.","author":"Chen Qi","year":"2021","unstructured":"Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In NeurIPS. 5199\u20135212."},{"key":"e_1_2_1_9_1","volume-title":"NeurIPS'21 competition track","author":"Approximate Nearest Neighbor Search Billion-Scale","year":"2021","unstructured":"Billion-Scale Approximate Nearest Neighbor Search Challenge: NeurIPS'21 competition track. 2021. https:\/\/big-annbenchmarks.com\/"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.1988.754602"},{"key":"e_1_2_1_11_1","unstructured":"Matthijs Douze Alexandr Guzhva Chengqi Deng Jeff Johnson Gergely Szilvasy Pierre-Emmanuel Mazar\u00e9 Maria Lomeli Lucas Hosseini and Herv\u00e9 J\u00e9gou. 2024. The Faiss library. (2024). arXiv:2401.08281 [cs.LG]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547308"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2021.3067706"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_15_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness."},{"key":"e_1_2_1_16_1","unstructured":"Tiezheng Ge Kaiming He Qifa Ke and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. 2946\u20132953."},{"key":"e_1_2_1_17_1","first-page":"3548","article-title":"Manu","volume":"15","author":"Guo Rentong","year":"2022","unstructured":"Rentong Guo, Xiaofan Luan, Long Xiang, Xiao Yan, Xiaomeng Yi, Jigao Luo, Qianya Cheng, Weizhi Xu, Jiarui Luo, Frank Liu, Zhenshan Cao, Yanliang Qiao, Ting Wang, Bo Tang, and Charles Xie. 2022. Manu: A Cloud Native Vector Database Management System. PVLDB. 15, 12 (2022), 3548\u20133561.","journal-title":"A Cloud Native Vector Database Management System. PVLDB."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Anupam Gupta Euiwoong Lee and Jason Li. 2019. The number of minimum k-cuts: improving the Karger-Stein bound. In STOC. 229\u2013240.","DOI":"10.1145\/3313276.3316395"},{"key":"e_1_2_1_19_1","volume-title":"FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713\u20135722.","author":"Harwood Ben","year":"2016","unstructured":"Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713\u20135722."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Jui-Ting Huang Ashish Sharma Shuying Sun Li Xia David Zhang Philip Pronin Janani Padmanabhan Giuseppe Ottaviano and Linjun Yang. 2020. Embedding-based Retrieval in Facebook Search. In KDD. 2553\u20132561.","DOI":"10.1145\/3394486.3403305"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604\u2013613.","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_2_1_24_1","unstructured":"The ChatGPT Retrieval Plugin lets you easily search and find personal or work documents by asking questionsin everyday language. 2023. https:\/\/github.com\/openai\/chatgpt-retrieval-plugin"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380600"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2964232"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489506"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Stanislav Morozov and Artem Babenko. 2019. Unsupervised Neural Quantization for Compressed-Domain Similarity Search. In ICCV. 3036\u20133045.","DOI":"10.1109\/ICCV.2019.00313"},{"key":"e_1_2_1_32_1","unstructured":"Joseph Naor and Yuval Rabani. 2001. Tree packing and approximating k-cuts. In SODA. 26\u201327."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588908"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Maria Predari and Aur\u00e9lien Esnard. 2016. A k-Way Greedy Graph Partitioning with Initial Fixed Vertices for Parallel Applications. In PDP. 280\u2013287.","DOI":"10.1109\/PDP.2016.109"},{"key":"e_1_2_1_35_1","first-page":"7803","article-title":"Graph-based Nearest Neighbor Search: From Practice to Theory","volume":"119","author":"Prokhorenkova Liudmila","year":"2020","unstructured":"Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based Nearest Neighbor Search: From Practice to Theory. In ICML, Vol. 119. 7803\u20137813.","journal-title":"ICML"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792251730"},{"key":"e_1_2_1_37_1","volume-title":"Ravishankar Krishnaswamy, and Rohan Kadekodi.","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. 2019. Rand-NSG: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS. 13748\u201313758."},{"key":"e_1_2_1_38_1","first-page":"39","article-title":"Approximate Nearest Neighbor Search in High Dimensional Vector Databases: Current Research and Future Directions","volume":"46","author":"Tian Yao","year":"2023","unstructured":"Yao Tian, Ziyang Yue, Ruiyuan Zhang, Xi Zhao, Bolong Zheng, and Xiaofang Zhou. 2023. Approximate Nearest Neighbor Search in High Dimensional Vector Databases: Current Research and Future Directions. IEEE Data Eng. Bull. 46, 3 (2023), 39\u201354.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Yao Tian Xi Zhao and Xiaofang Zhou. 2022. DB-LSH: Locality-Sensitive Hashing with Query-based Dynamic Bucketing. In ICDE. 2250\u20132262.","DOI":"10.1109\/ICDE53745.2022.00214"},{"key":"e_1_2_1_40_1","unstructured":"Michael Tschannen Manoj Kumar Andreas Steiner Xiaohua Zhai Neil Houlsby and Lucas Beyer. 2023. Image Captioners Are Scalable Vision Learners Too. In NeurIPS."},{"key":"e_1_2_1_41_1","volume-title":"A note on graph-based nearest neighbor search. arXiv preprint arXiv:2012.11083","author":"Wang Hongya","year":"2020","unstructured":"Hongya Wang, Zhizheng Wang, Wei Wang, Yingyuan Xiao, Zeng Zhao, and Kaixiang Yang. 2020. A note on graph-based nearest neighbor search. arXiv preprint arXiv:2012.11083 (2020)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639269"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Xi Zhao Zhonghan Chen Kai Huang Ruiyuan Zhang Bolong Zheng and Xiaofang Zhou. 2024. Efficient Approximate Maximum Inner Product Search Over Sparse Vectors. In ICDE. 3961\u20133974.","DOI":"10.1109\/ICDE60146.2024.00303"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594527"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579084"},{"key":"e_1_2_1_47_1","volume-title":"Jensen","author":"Zheng Bolong","year":"2023","unstructured":"Bolong Zheng, Ziyang Yue, Qi Hu, Xiaomeng Yi, Xiaofan Luan, Charles Xie, Xiaofang Zhou, and Christian S. Jensen. 2023. Learned Probing Cardinality Estimation for High-Dimensional Approximate NN Search. In ICDE. 3209\u20133221."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377374"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00680-7"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749697","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T03:14:16Z","timestamp":1757042056000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749697"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":49,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749697"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749697","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}