{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:09:48Z","timestamp":1785542988172,"version":"3.56.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p>Approximate nearest neighbor search (ANNS) is a fundamental problem that has a wide range of applications in information retrieval and data mining. Among state-of-the-art in-memory ANNS methods, graph-based methods have attracted particular interest owing to their superior efficiency and query accuracy. Most of these methods focus on the selection of edges to shorten the search path, but do not pay much attention to the computational cost at each hop. To reduce the cost, we propose a novel graph structure called HVS. HVS has a hierarchical structure of multiple layers that corresponds to a series of subspace divisions in a coarse-to-fine manner. In addition, we utilize a virtual Voronoi diagram in each layer to accelerate the search. By traversing Voronoi cells, HVS can reach the nearest neighbors of a given query efficiently, resulting in a reduction in the total search cost. Experiments confirm that HVS is superior to other state-of-the-art graph-based methods.<\/jats:p>","DOI":"10.14778\/3489496.3489506","type":"journal-article","created":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:28:36Z","timestamp":1644020916000},"page":"246-258","source":"Crossref","is-referenced-by-count":49,"title":["HVS"],"prefix":"10.14778","volume":"15","author":[{"given":"Kejing","family":"Lu","sequence":"first","affiliation":[{"name":"Nagoya University, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mineichi","family":"Kudo","sequence":"additional","affiliation":[{"name":"Hokkaido University, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chuan","family":"Xiao","sequence":"additional","affiliation":[{"name":"Osaka University, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yoshiharu","family":"Ishikawa","sequence":"additional","affiliation":[{"name":"Nagoya University, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,2,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Jianping Fan, Ahmed K. Elmagarmid, Moustafa A. Hammad, Ihab F. Ilyas, Mirette S. Marzouk, and Xingquan Zhu.","author":"Aref Walid G.","year":"2002","unstructured":"Walid G. Aref , Ann Christine Catlin , Jianping Fan, Ahmed K. Elmagarmid, Moustafa A. Hammad, Ihab F. Ilyas, Mirette S. Marzouk, and Xingquan Zhu. 2002 . A Video Database Management System for Advancing Video Database Research. In Multimedia Information Systems . 8--17. Walid G. Aref, Ann Christine Catlin, Jianping Fan, Ahmed K. Elmagarmid, Moustafa A. Hammad, Ihab F. Ilyas, Mirette S. Marzouk, and Xingquan Zhu. 2002. A Video Database Management System for Advancing Video Database Research. In Multimedia Information Systems. 8--17."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313768"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219973"},{"key":"e_1_2_1_4_1","unstructured":"Dmitry Baranchuk Dmitry Persiyanov Anton Sinitsin and Artem Babenko. 2019. Learning to Route in Similarity Graphs. In ICML. 475--484.  Dmitry Baranchuk Dmitry Persiyanov Anton Sinitsin and Artem Babenko. 2019. Learning to Route in Similarity Graphs. In ICML. 475--484."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2875145"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3227609.3227643"},{"key":"e_1_2_1_7_1","volume-title":"SPTAG: A library for fast approximate nearest neighbor search. https:\/\/github.com\/Microsoft\/SPTAG","author":"Chen Qi","year":"2018","unstructured":"Qi Chen , Haidong Wang , Mingqin Li , Gang Ren , Scarlett Li , Jeffery Zhu , Jason Li , Chuanjie Liu , Lintao Zhang , and Jingdong Wang . 2018 . SPTAG: A library for fast approximate nearest neighbor search. https:\/\/github.com\/Microsoft\/SPTAG Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search. https:\/\/github.com\/Microsoft\/SPTAG"},{"key":"e_1_2_1_8_1","first-page":"548","article-title":"Monotonic search networks for computer vision databases","volume":"2","author":"Dearholt D.","year":"1988","unstructured":"D. Dearholt , N. Gonzales , and G. Kurup . 1988 . Monotonic search networks for computer vision databases . Signals, Systems and Computers 2 (1988), 548 -- 553 . D. Dearholt, N. Gonzales, and G. Kurup. 1988. Monotonic search networks for computer vision databases. Signals, Systems and Computers 2 (1988), 548--553.","journal-title":"Signals, Systems and Computers"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Matthijs Douze Alexandre Sablayrolles and Herv\u00e9 J\u00e9gou. 2018. Fast indexing with graphs and compact regression codes. In CVPR. 3646--3654.  Matthijs Douze Alexandre Sablayrolles and Herv\u00e9 J\u00e9gou. 2018. Fast indexing with graphs and compact regression codes. In CVPR. 3646--3654.","DOI":"10.1109\/CVPR.2018.00384"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368303"},{"key":"e_1_2_1_12_1","volume-title":"Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. In arXiv:1609.07228.","author":"Fu Cong","year":"2016","unstructured":"Cong Fu and Deng Cai . 2016 . Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. In arXiv:1609.07228. Cong Fu and Deng Cai. 2016. Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. In arXiv:1609.07228."},{"key":"e_1_2_1_13_1","volume-title":"High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility","author":"Fu Cong","year":"2021","unstructured":"Cong Fu , Changxu Wang , and Deng Cai . 2021. High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility . IEEE Trans. Pattern Anal. Mach. Intell ( 2021 ). Cong Fu, Changxu Wang, and Deng Cai. 2021. High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE Trans. Pattern Anal. Mach. Intell (2021)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.240"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380184"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283516.2283615"},{"key":"e_1_2_1_18_1","volume-title":"FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713--5722.","author":"Harwood Ben","year":"2016","unstructured":"Ben Harwood and Tom Drummond . 2016 . FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713--5722. Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713--5722."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0472-7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2014.2302018"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1027527.1027729"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389778"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380600"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Jie Liu Xiao Yan Xinyan Dai Zhirong Li James Cheng and Ming-Chang Yang. 2020. Understanding and Improving Proximity Graph based Maximum Inner Product Search. In AAAI. 139--146.  Jie Liu Xiao Yan Xinyan Dai Zhirong Li James Cheng and Ming-Chang Yang. 2020. Understanding and Improving Proximity Graph based Maximum Inner Product Search. In AAAI. 139--146.","DOI":"10.1609\/aaai.v34i01.5344"},{"key":"e_1_2_1_27_1","unstructured":"Kejing Lu and Mineichi Kudo. 2020. R2LSH: A Nearest Neighbor Search Scheme Based on Two-dimensional Projected Spaces. In ICDE. 1045--1056.  Kejing Lu and Mineichi Kudo. 2020. R2LSH: A Nearest Neighbor Search Scheme Based on Two-dimensional Projected Spaces. In ICDE. 1045--1056."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397240"},{"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","unstructured":"Marius Muja. 2019. https:\/\/github.com\/flann-lib\/flann.  Marius Muja. 2019. https:\/\/github.com\/flann-lib\/flann."},{"key":"e_1_2_1_32_1","unstructured":"Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based Nearest Neighbor Search: From Practice to Theory. In ICML. 7803--7813.  Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based Nearest Neighbor Search: From Practice to Theory. In ICML. 7803--7813."},{"key":"e_1_2_1_33_1","unstructured":"Alexandre Sablayrolles Matthijs Douze Cordelia Schmid and Herv\u00e9 J\u00e9gou. 2019. Spreading vectors for similarity search. In ICLR.  Alexandre Sablayrolles Matthijs Douze Cordelia Schmid and Herv\u00e9 J\u00e9gou. 2019. Spreading vectors for similarity search. In ICLR."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_35_1","volume-title":"Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search. Pattern Recognition 96","author":"Mu\u00f1oz Javier Vargas","year":"2019","unstructured":"Javier Vargas Mu\u00f1oz , Marcos A. Gon\u00e7alves , Zanoni Dias , and Ricardo da S. Torres . 2019. Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search. Pattern Recognition 96 ( 2019 ). Javier Vargas Mu\u00f1oz, Marcos A. Gon\u00e7alves, Zanoni Dias, and Ricardo da S. Torres. 2019. Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search. Pattern Recognition 96 (2019)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357938"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3455025"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3489496.3489506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:11:55Z","timestamp":1672225915000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3489496.3489506"}},"subtitle":["hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search"],"short-title":[],"issued":{"date-parts":[[2021,10]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.14778\/3489496.3489506"],"URL":"https:\/\/doi.org\/10.14778\/3489496.3489506","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,10]]}}}