{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:06Z","timestamp":1779174846311,"version":"3.51.4"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:p>\n            Proximity graphs (PG) have gained increasing popularity as the state-of-the-art solutions to\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -approximate nearest neighbor (\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -ANN) search on high-dimensional data, which serves as a fundamental function in various fields, e.g., retrieval-augmented generation. Although PG-based approaches have the best\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -ANN search performance, their index construction cost is superlinear to the number of points. Such superlinear cost substantially limits their scalability in the era of big data. Hence, the goal of this paper is to accelerate the construction of PG-based methods without compromising their\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -ANN search performance.\n          <\/jats:p>\n          <jats:p>\n            To achieve this goal, two mainstream categories of PG are revisited: relative neighborhood graph (RNG) and navigable small world graph (NSWG). By revisiting their construction process, we find the issues of construction efficiency. To address these issues, we propose a new construction framework with a novel pruning strategy for edge selection, which accelerates RNG construction while keeping its\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -ANN search performance. Then, we integrate this framework into NSWG construction to enhance both the construction efficiency and\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -ANN search performance of NSWG. Extensive experiments are conducted to validate our construction framework for both RNG and NSWG, and that it significantly reduces the PG construction cost, achieving up to 5.6x speedup, while not compromising the\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -ANN search performance.\n          <\/jats:p>","DOI":"10.14778\/3725688.3725709","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:19:21Z","timestamp":1756477161000},"page":"1825-1838","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search"],"prefix":"10.14778","volume":"18","author":[{"given":"Shuo","family":"Yang","sequence":"first","affiliation":[{"name":"Xidian University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiadong","family":"Xie","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yingfan","family":"Liu","sequence":"additional","affiliation":[{"name":"Xidian University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiyue","family":"Gao","sequence":"additional","affiliation":[{"name":"Xidian University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qianru","family":"Wang","sequence":"additional","affiliation":[{"name":"Xidian University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanguo","family":"Peng","sequence":"additional","affiliation":[{"name":"Xidian University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiangtao","family":"Cui","sequence":"additional","affiliation":[{"name":"Xidian University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2010. Datasets for approximate nearest neighbor search. http:\/\/corpus-texmex.irisa.fr\/."},{"key":"e_1_2_1_2_1","unstructured":"2023. Common Crawl. https:\/\/commoncrawl.org\/."},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"A GPU Algorithm for Detecting Strongly Connected Components","volume":"17","author":"Alabandi Ghadeer","year":"2023","unstructured":"Ghadeer Alabandi, William Sands, George Biros, and Martin Burtscher. 2023. A GPU Algorithm for Detecting Strongly Connected Components. In SC. ACM, 17:1\u201317:13.","journal-title":"SC. ACM"},{"key":"e_1_2_1_4_1","volume-title":"Retrieval-based Language Models and Applications. ACL Tutorial","author":"Asai Akari","year":"2023","unstructured":"Akari Asai, Sewon Min, Zexuan Zhong, and Danqi Chen. 2023. Retrieval-based Language Models and Applications. ACL Tutorial (2023)."},{"key":"e_1_2_1_5_1","volume-title":"ANNBenchmarks: 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. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst. 87 (2020)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","article-title":"Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure","volume":"23","author":"Aurenhammer Franz","year":"1991","unstructured":"Franz Aurenhammer. 1991. Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Comput. Surv. 23, 3 (1991), 345\u2013405.","journal-title":"ACM Comput. Surv."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1109\/TPAMI.2014.2361319","article-title":"The inverted multi-index","volume":"37","author":"Babenko Artem","year":"2014","unstructured":"Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE TPAMI 37, 6 (2014), 1247\u20131260.","journal-title":"IEEE TPAMI"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 27th ACM International Conference on Multimedia. 2202\u20132204","author":"Barthel Kai Uwe","year":"2019","unstructured":"Kai Uwe Barthel, Nico Hezel, Konstantin Schall, and Klaus Jung. 2019. Real-time visual navigation in huge image sets using similarity graphs. In Proceedings of the 27th ACM International Conference on Multimedia. 2202\u20132204."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary search trees used for associative searching","volume":"18","author":"Bentley Jon Louis","year":"1975","unstructured":"Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509\u2013517.","journal-title":"Commun. ACM"},{"key":"e_1_2_1_10_1","volume-title":"The X-tree: An Index Structure for High-Dimensional Data. In VLDB. 28\u201339.","author":"Berchtold Stefan","year":"1996","unstructured":"Stefan Berchtold, Daniel A. Keim, and Hans-Peter Kriegel. 1996. The X-tree: An Index Structure for High-Dimensional Data. In VLDB. 28\u201339."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 12th International Society for Music Information Retrieval Conference, ISMIR 2011","author":"Bertin-Mahieux Thierry","year":"2011","unstructured":"Thierry Bertin-Mahieux, Daniel P. W. Ellis, Brian Whitman, and Paul Lamere. 2011. The Million Song Dataset. In Proceedings of the 12th International Society for Music Information Retrieval Conference, ISMIR 2011. University of Miami, 591\u2013596."},{"key":"e_1_2_1_12_1","first-page":"1989","article-title":"Fast approximate kNN graph construction for high dimensional data via recursive Lanczos bisection","volume":"10","author":"Chen Jie","year":"2009","unstructured":"Jie Chen, Haw Ren Fang, and Yousef Saad. 2009. Fast approximate kNN graph construction for high dimensional data via recursive Lanczos bisection. Journal of Machine Learning Research 10, 9 (2009), 1989\u20132012.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_13_1","volume-title":"SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search. In 35th Conference on Neural Information Processing Systems (NeurIPS","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 Neighbor Search. In 35th Conference on Neural Information Processing Systems (NeurIPS 2021)."},{"key":"e_1_2_1_14_1","volume-title":"Mirrokni","author":"Datar Mayur","year":"2004","unstructured":"Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In SoCG. 253\u2013262."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Wei Dong Charikar Moses and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW. 577\u2013586.","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_16_1","first-page":"4139","article-title":"High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility","volume":"44","author":"Fu Cong","year":"2022","unstructured":"Cong Fu, Changxu Wang, and Deng Cai. 2022. High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE TPAMI 44, 8 (2022), 4139\u20134150.","journal-title":"IEEE TPAMI"},{"key":"e_1_2_1_17_1","first-page":"461","article-title":"Fast approximate nearest neighbor search with the navigating spreading-out graph","volume":"12","author":"Fu Cong","year":"2019","unstructured":"Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. PVLDB 12, 5 (2019), 461\u2013474.","journal-title":"PVLDB"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Junhao Gan Jianlin Feng Qiong Fang and Wilfred Ng. 2012. Locality Sensitive Hashing Scheme Based on Dyanmic Collision Counting. In SIGMOD. 541\u2013552.","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the ACM Web Conference","author":"Gollapudi Siddharth","year":"2023","unstructured":"Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. 2023. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In Proceedings of the ACM Web Conference 2023. ACM, 3406\u20133416."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Mihajlo Grbovic and Haibin Cheng. 2018. SIGKDD Yike Guo and Faisal Farooq (Eds.). ACM 311\u2013320.","DOI":"10.1145\/3219819.3219885"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1109\/TBDATA.2022.3161156","article-title":"GGNN: Graph-based gpu nearest neighbor search","volume":"9","author":"Groh Fabian","year":"2022","unstructured":"Fabian Groh, Lukas Ruppert, Patrick Wieschollek, and Hendrik PA Lensch. 2022. GGNN: Graph-based gpu nearest neighbor search. IEEE Transactions on Big Data 9, 1 (2022), 267\u2013279.","journal-title":"IEEE Transactions on Big Data"},{"key":"e_1_2_1_22_1","unstructured":"Kelvin Guu Kenton Lee Zora Tung Panupong Pasupat and Mingwei Chang. 2020. Retrieval augmented language model pre-training. In ICML. 3929\u20133938."},{"key":"e_1_2_1_23_1","volume-title":"FANNG: Fast Approximate Nearest Neighbour Graphs. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR","author":"Harwood Ben","year":"2016","unstructured":"Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016. IEEE Computer Society, 5713\u20135722."},{"key":"e_1_2_1_24_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. [n. d.]. Embedding-based Retrieval in Facebook Search. In KDD. 2553\u20132561.","DOI":"10.1145\/3394486.3403305"},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"Query-aware locality-sensitive hashing for approximate nearest neighbor search","volume":"9","author":"Huang Qiang","year":"2016","unstructured":"Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2016. Query-aware locality-sensitive hashing for approximate nearest neighbor search. PVLDB 9, 1 (2016), 1\u201312.","journal-title":"PVLDB"},{"key":"e_1_2_1_26_1","first-page":"1","article-title":"Atlas: Few-shot learning with retrieval augmented language models","volume":"24","author":"Izacard Gautier","year":"2023","unstructured":"Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi-Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave. 2023. Atlas: Few-shot learning with retrieval augmented language models. JMLR 24, 251 (2023), 1\u201343.","journal-title":"JMLR"},{"key":"e_1_2_1_27_1","volume-title":"Harsha Vardhan Simhadri, and Sheshansh Agrawal","author":"Jaiswal Shikhar","year":"2022","unstructured":"Shikhar Jaiswal, Ravishankar Krishnaswamy, Ankit Garg, Harsha Vardhan Simhadri, and Sheshansh Agrawal. 2022. OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries. CoRR abs\/2211.12850 (2022)."},{"key":"e_1_2_1_28_1","volume-title":"Ravishankar Krishnawamy, and Rohan Kadekodi.","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Advances in Neural Information Processing Systems, Vol. 32. Curran Associates, Inc."},{"key":"e_1_2_1_29_1","volume-title":"Product quantization for nearest neighbor search","author":"Jegou Herve","year":"2011","unstructured":"Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2011. Product quantization for nearest neighbor search. IEEE TPAMI 33(1) (2011), 117\u2013128."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Norio Katayama and Shin'ichi Satoh. 1997. The SR-tree: an index structure for high-dimensional nearest neighbor queries. In SIGMOD. 369\u2013380.","DOI":"10.1145\/253262.253347"},{"key":"e_1_2_1_31_1","first-page":"9459","article-title":"Retrieval-augmented generation for knowledge-intensive NLP tasks","volume":"33","author":"Lewis Patrick","year":"2020","unstructured":"Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich K\u00fcttler, Mike Lewis, Wen-tau Yih, Tim Rockt\u00e4schel, et al. 2020. Retrieval-augmented generation for knowledge-intensive NLP tasks. NeurIPS 33 (2020), 9459\u20139474.","journal-title":"NeurIPS"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference","author":"Li Conglong","year":"2020","unstructured":"Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. 2020. Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020. ACM, 2539\u20132554."},{"key":"e_1_2_1_33_1","first-page":"1475","article-title":"Approximate nearest neighbor search on high dimensional data - experiments, analyses, and improvement","volume":"32","author":"Li Wen","year":"2019","unstructured":"Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional data - experiments, analyses, and improvement. IEEE TKDE 32, 8 (2019), 1475\u20131488.","journal-title":"IEEE TKDE"},{"key":"e_1_2_1_34_1","unstructured":"Di Liu Meng Chen Baotong Lu Huiqiang Jiang Zhenhua Han Qianxi Zhang Qi Chen Chengruidong Zhang Bailu Ding Kai Zhang et al. 2024. RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval. arXiv preprint arXiv:2409.10516 (2024)."},{"key":"e_1_2_1_35_1","volume-title":"Retrieval Attention: Accelerating Long-Context LLM Inference via Vector Retrieval. arXiv:2409.10516 [cs.LG]","author":"Liu Di","year":"2024","unstructured":"Di Liu, Meng Chen, Baotong Lu, Huiqiang Jiang, Zhenhua Han, Qianxi Zhang, Qi Chen, Chengruidong Zhang, Bailu Ding, Kai Zhang, Chen Chen, Fan Yang, Yuqing Yang, and Lili Qiu. 2024. Retrieval Attention: Accelerating Long-Context LLM Inference via Vector Retrieval. arXiv:2409.10516 [cs.LG]"},{"key":"e_1_2_1_36_1","first-page":"745","article-title":"SK-LSH: an efficient index structure for approximate nearest neighbor search","volume":"7","author":"Liu Yingfan","year":"2014","unstructured":"Yingfan Liu, Jiangtao Cui, Zi Huang, Hui Li, and Hengtao shen. 2014. SK-LSH: an efficient index structure for approximate nearest neighbor search. PVLDB 7, 9 (2014), 745\u2013756.","journal-title":"PVLDB"},{"key":"e_1_2_1_37_1","volume-title":"Zhe Wang, Moses Charikar, and Kai Li.","author":"Lv Qin","year":"2007","unstructured":"Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multiprobe LSH: efficient indexing for high-dimensional similarity search. In VLDB. 950\u2013961."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.is.2013.10.006","article-title":"Approximate nearest neighbor algorithm based on navigable small world graphs","volume":"45","author":"Malkov Yury","year":"2014","unstructured":"Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61\u201368.","journal-title":"Information Systems"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1109\/TPAMI.2018.2889473","article-title":"Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs","volume":"42","author":"Malkov Yury","year":"2018","unstructured":"Yury Malkov and Dmitry Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE TPAMI 42, 4 (2018), 824\u2013836.","journal-title":"IEEE TPAMI"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP","author":"Manohar Magdalen Dobson","year":"2024","unstructured":"Magdalen Dobson Manohar, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP 2024. ACM, 270\u2013285."},{"key":"e_1_2_1_41_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press."},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","first-page":"2227","DOI":"10.1109\/TPAMI.2014.2321376","article-title":"Scalable nearest neighbor algorithms for high dimensional data","volume":"36","author":"Muja Marius","year":"2014","unstructured":"Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. IEEE TPAMI 36, 11 (2014), 2227\u20132240.","journal-title":"IEEE TPAMI"},{"key":"e_1_2_1_43_1","volume-title":"Efficient Page-based Search over Isomorphic Mapped Graph Index using Query-sensitivity Entry Vertex. CoRR abs\/2310.00402","author":"Ni Jiongkang","year":"2023","unstructured":"Jiongkang Ni, Xiaoliang Xu, Yuxiang Wang, Can Li, Jiajie Yao, Shihai Xiao, and Xuecang Zhang. 2023. DiskANN++: Efficient Page-based Search over Isomorphic Mapped Graph Index using Query-sensitivity Entry Vertex. CoRR abs\/2310.00402 (2023)."},{"key":"e_1_2_1_44_1","volume-title":"SIGKDD. ACM","author":"Okura Shumpei","year":"2017","unstructured":"Shumpei Okura, Yukihiro Tagami, Shingo Ono, and Akira Tajima. 2017. Embedding-based News Recommendation for Millions of Users. In SIGKDD. ACM, 1933\u20131942."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 31st ACM International Conference on Multimedia, MM 2023. ACM, 1659\u20131667","author":"Ono Naoki","year":"2023","unstructured":"Naoki Ono and Yusuke Matsui. 2023. Relative NN-Descent: A Fast Index Construction for Graph-Based Approximate Nearest Neighbor Search. In Proceedings of the 31st ACM International Conference on Multimedia, MM 2023. ACM, 1659\u20131667."},{"key":"e_1_2_1_46_1","volume-title":"CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs. arXiv:2308.15136","author":"Ootomo Hiroyuki","year":"2023","unstructured":"Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, and Yong Wang. 2023. CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs. arXiv:2308.15136 (2023). arXiv:2308.15136 [cs.DS]"},{"key":"e_1_2_1_47_1","volume-title":"Vector Database Management Techniques and Systems. In Companion of the 2024 International Conference on Management of Data. ACM, 597\u2013604","author":"Pan James Jie","year":"2024","unstructured":"James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Vector Database Management Techniques and Systems. In Companion of the 2024 International Conference on Management of Data. ACM, 597\u2013604."},{"key":"e_1_2_1_48_1","first-page":"1","volume-title":"Proc. ACM Manag. Data 1","author":"Peng Yun","year":"2023","unstructured":"Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proc. ACM Manag. Data 1, 1 (2023), 54:1\u201354:27."},{"key":"e_1_2_1_49_1","volume-title":"Manning","author":"Pennington Jeffrey","year":"2014","unstructured":"Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. Glove: Global Vectors for Word Representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, A meeting of SIGDAT, a Special Interest Group of the ACL. ACL, 1532\u20131543."},{"key":"e_1_2_1_50_1","volume-title":"NeurIPS","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy, and Harsha Simhadri. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS 2019."},{"key":"e_1_2_1_51_1","first-page":"1","article-title":"SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index","volume":"8","author":"Sun Yifang","year":"2015","unstructured":"Yifang Sun, Wei Wang, Jianbin Qin, Ying Zhang, and Xuemin Lin. 2015. SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index. PVLDB 8, 1 (2015), 1\u201312.","journal-title":"PVLDB"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Yufei Tao Ke Yi Cheng Sheng and Panos Kalnis. 2009. Quality and efficiency in high dimensional nearest neighbor search. In SIGMOD. 563\u2013576.","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_53_1","volume-title":"Social networks","author":"Travers Jeffrey","unstructured":"Jeffrey Travers and Stanley Milgram. 1977. An experimental study of the small world problem. In Social networks. Elsevier, 179\u2013197."},{"key":"e_1_2_1_54_1","volume-title":"CIKM. ACM","author":"Wang Hui","year":"2021","unstructured":"Hui Wang, Wan-Lei Zhao, Xiangxiang Zeng, and Jianye Yang. 2021. Fast k-NN Graph Construction by GPU based NN-Descent. In CIKM. ACM, 1929\u20131938."},{"key":"e_1_2_1_55_1","volume-title":"Milvus: A Purpose-Built Vector Data Management System. In SIGMOD '21: International Conference on Management of Data. ACM, 2614\u20132627","author":"Wang Jianguo","year":"2021","unstructured":"Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD '21: International Conference on Management of Data. ACM, 2614\u20132627."},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/TPAMI.2017.2699960","article-title":"A survey on learning to hash","volume":"40","author":"Wang Jingdong","year":"2017","unstructured":"Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, and Heng Tao Shen. 2017. A survey on learning to hash. IEEE TPAMI 40, 4 (2017), 769\u2013790.","journal-title":"IEEE TPAMI"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3639269","article-title":"Starling: An I\/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment","volume":"2","author":"Wang Mengzhao","year":"2024","unstructured":"Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I\/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment. Proceedings of the ACM on Management of Data 2, 1 (2024), 1\u201327.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_58_1","first-page":"1964","article-title":"A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search","volume":"14","author":"Wang Mengzhao","year":"2021","unstructured":"Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. PVLDB 14, 11 (2021), 1964\u20131978.","journal-title":"PVLDB"},{"key":"e_1_2_1_59_1","volume-title":"Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiangtao Cui.","author":"Yang Shuo","year":"2024","unstructured":"Shuo Yang, Jiadong Xie, Yingfan Liu, Jeffrey Xu Yu, Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiangtao Cui. 2024. Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search. CoRR abs\/2410.01231 (2024)."},{"key":"e_1_2_1_60_1","volume-title":"GPU-accelerated proximity graph approximate nearest Neighbor search and construction","author":"Yu Yuanhang","unstructured":"Yuanhang Yu, Dong Wen, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2022. GPU-accelerated proximity graph approximate nearest Neighbor search and construction. In ICDE. IEEE, 552\u2013564."},{"key":"e_1_2_1_61_1","volume-title":"17th USENIX Symposium on Operating Systems Design and Implementation, OSDI","author":"Zhang Qianxi","year":"2023","unstructured":"Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In 17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023. USENIX Association, 377\u2013395."},{"key":"e_1_2_1_62_1","volume-title":"SONG: Approximate nearest neighbor search on gpu","author":"Zhao Weijie","year":"2020","unstructured":"Weijie Zhao, Shulong Tan, and Ping Li. 2020. SONG: Approximate nearest neighbor search on gpu. In ICDE. IEEE, 1033\u20131044."},{"key":"e_1_2_1_63_1","first-page":"1979","article-title":"Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces","volume":"16","author":"Zhao Xi","year":"2023","unstructured":"Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces. PVLDB 16, 8 (2023), 1979\u20131991.","journal-title":"PVLDB"},{"key":"e_1_2_1_64_1","first-page":"1","volume-title":"Proc. ACM Manag. Data 2","author":"Zuo Chaoji","year":"2024","unstructured":"Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 1 (2024), 69:1\u201369:26."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3725688.3725709","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T14:19:31Z","timestamp":1756477171000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3725688.3725709"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2]]},"references-count":64,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["10.14778\/3725688.3725709"],"URL":"https:\/\/doi.org\/10.14778\/3725688.3725709","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,2]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}