{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:38:39Z","timestamp":1780346319741,"version":"3.54.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>Approximate nearest neighbor search (ANNS) is a fundamental problem in databases and data mining. A scalable ANNS algorithm should be both memory-efficient and fast. Some early graph-based approaches have shown attractive theoretical guarantees on search time complexity, but they all suffer from the problem of high indexing time complexity. Recently, some graph-based methods have been proposed to reduce indexing complexity by approximating the traditional graphs; these methods have achieved revolutionary performance on million-scale datasets. Yet, they still can not scale to billion-node databases. In this paper, to further improve the search-efficiency and scalability of graph-based methods, we start by introducing four aspects: (1) ensuring the connectivity of the graph; (2) lowering the average out-degree of the graph for fast traversal; (3) shortening the search path; and (4) reducing the index size. Then, we propose a novel graph structure called Monotonic Relative Neighborhood Graph (MRNG) which guarantees very low search complexity (close to logarithmic time). To further lower the indexing complexity and make it practical for billion-node ANNS problems, we propose a novel graph structure named Navigating Spreading-out Graph (NSG) by approximating the MRNG. The NSG takes the four aspects into account simultaneously. Extensive experiments show that NSG outperforms all the existing algorithms significantly. In addition, NSG shows superior performance in the E-commercial scenario of Taobao (Alibaba Group) and has been integrated into their billion-scale search engine.<\/jats:p>","DOI":"10.14778\/3303753.3303754","type":"journal-article","created":{"date-parts":[[2019,2,27]],"date-time":"2019-02-27T14:57:56Z","timestamp":1551279476000},"page":"461-474","source":"Crossref","is-referenced-by-count":281,"title":["Fast approximate nearest neighbor search with the navigating spreading-out graph"],"prefix":"10.14778","volume":"12","author":[{"given":"Cong","family":"Fu","sequence":"first","affiliation":[{"name":"Zhejiang University, China and Alibaba-Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chao","family":"Xiang","sequence":"additional","affiliation":[{"name":"Zhejiang University, China and Alibaba-Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Changxu","family":"Wang","sequence":"additional","affiliation":[{"name":"Zhejiang University, China and Alibaba-Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deng","family":"Cai","sequence":"additional","affiliation":[{"name":"Zhejiang University, China and Alibaba-Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856324"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204034"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313768"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_1_5_1","first-page":"2055","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition","author":"Babenko A.","year":"2016"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98741"},{"key":"e_1_2_1_7_1","first-page":"5713","volume-title":"Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition","author":"Ben H.","year":"2016"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1130"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066213"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSP.2005.1628631"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564729"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.1988.754602"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_15_1","unstructured":"C. Fu and D. Cai. Efanna : An extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv:1609.07228 2016.  C. Fu and D. Cai. Efanna : An extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv:1609.07228 2016."},{"key":"e_1_2_1_16_1","unstructured":"C. Fu C. Xiang C. Wang and D. Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv: 1707.00143 2018.  C. Fu C. Xiang C. Wang and D. Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv: 1707.00143 2018."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1975.224297"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588565"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.379"},{"key":"e_1_2_1_20_1","first-page":"518","volume-title":"PVLDB","author":"Gionis A.","year":"1999"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence, 22: 1312--1317","author":"Hajebi K.","year":"2011"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a014"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163414"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Z. Jin D. Zhang Y. Hu S. Lin D. Cai and X. He. Fast and accurate hashing via iterative nearest neighbors expansion. IEEE transactions on cybernetics 44(11):2167--2177 2014.  Z. Jin D. Zhang Y. Hu S. Lin D. Cai and X. He. Fast and accurate hashing via iterative nearest neighbors expansion. IEEE transactions on cybernetics 44(11):2167--2177 2014.","DOI":"10.1109\/TCYB.2014.2302018"},{"key":"e_1_2_1_28_1","unstructured":"J. Johnson M. Douze and H. J\u00e9gou. Billion-scale similarity search with gpus. arXiv:1702.08734 2017.  J. Johnson M. Douze and H. J\u00e9gou. Billion-scale similarity search with gpus. arXiv:1702.08734 2017."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"e_1_2_1_30_1","volume-title":"New Mexico State University","author":"Kurup G. D.","year":"1992"},{"key":"e_1_2_1_31_1","unstructured":"W. Li Y. Zhang Y. Sun W. Wang W. Zhang and X. Lin. Approximate nearest neighbor search on high dimensional data---experiments analyses and improvement (v1. 0). arXiv:1610.02455 2016.  W. Li Y. Zhang Y. Sun W. Wang W. Zhang and X. Lin. Approximate nearest neighbor search on high dimensional data---experiments analyses and improvement (v1. 0). arXiv:1610.02455 2016."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732947"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_34_1","unstructured":"Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. arXiv:1603.09320 2016.  Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. arXiv:1603.09320 2016."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"C. D. Manning P. Raghavan H. Sch\u00fctze etal Introduction to information retrieval. Cambridge university press Cambridge 1(1) 2008.   C. D. Manning P. Raghavan H. Sch\u00fctze et al. Introduction to information retrieval. Cambridge university press Cambridge 1(1) 2008.","DOI":"10.1017\/CBO9780511809071"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587638"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0329-7"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(80)90066-7"},{"key":"e_1_2_1_39_1","first-page":"194","article-title":"A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces","volume":"98","author":"Weber R.","year":"1998","journal-title":"PVLDB"},{"key":"e_1_2_1_40_1","unstructured":"Y. Weiss A. Torralba and R. Fergus. Spectral hashing. Advances in neural information processing systems pages 1753--1760 2009.   Y. Weiss A. Torralba and R. Fergus. Spectral hashing. Advances in neural information processing systems pages 1753--1760 2009."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610500"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882930"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3303753.3303754","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:26:34Z","timestamp":1672219594000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3303753.3303754"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.14778\/3303753.3303754"],"URL":"https:\/\/doi.org\/10.14778\/3303753.3303754","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}