{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:04:18Z","timestamp":1775815458413,"version":"3.50.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:p>\n            Top-\n            <jats:italic>k<\/jats:italic>\n            Nearest Neighbors (\n            <jats:italic>k<\/jats:italic>\n            NN) problem on road network has numerous applications on location-based services. As direct search using the Dijkstra's algorithm results in a large search space, a plethora of complex-index-based approaches have been proposed to speedup the query processing. However, even with the current state-of-the-art approach, long query processing delays persist, along with significant space overhead and prohibitively long indexing time. In this paper, we depart from the complex index designs prevalent in existing literature and propose a simple index named KNN-Index. With KNN-Index, we can answer a\n            <jats:italic>k<\/jats:italic>\n            NN query optimally and progressively with small and size-bounded index. To improve the index construction performance, we propose a bidirectional construction algorithm which can effectively share the common computation during the construction. Theoretical analysis and experimental results on real road networks demonstrate the superiority of KNN-Index over the state-of-the-art approach in query processing performance, index size, and index construction efficiency.\n          <\/jats:p>","DOI":"10.14778\/3704965.3704975","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:22:57Z","timestamp":1739899377000},"page":"4683-4695","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks"],"prefix":"10.14778","volume":"17","author":[{"given":"Yiqi","family":"Wang","sequence":"first","affiliation":[{"name":"Nanjing University of Science and Technology, The University of New South Wales"}]},{"given":"Long","family":"Yuan","sequence":"additional","affiliation":[{"name":"Nanjing University of Science and Technology"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales"}]},{"given":"Zi","family":"Chen","sequence":"additional","affiliation":[{"name":"Nanjing University of Aeronautics and Astronautics"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiaotong University"}]},{"given":"Qing","family":"Liu","sequence":"additional","affiliation":[{"name":"Data61, CSIRO, Australia"}]}],"member":"320","published-online":{"date-parts":[[2025,2,18]]},"reference":[{"key":"e_1_2_1_1_1","article-title":"A survey on nearest neighbor search methods","volume":"95","author":"Abbasifard Mohammad Reza","year":"2014","unstructured":"Mohammad Reza Abbasifard, Bijan Ghahremani, and Hassan Naderi. 2014. A survey on nearest neighbor search methods. International Journal of Computer Applications 95, 25 (2014).","journal-title":"International Journal of Computer Applications"},{"key":"e_1_2_1_2_1","unstructured":"Airnb. [n.d.]. https:\/\/www.airbnb.com\/."},{"key":"e_1_2_1_3_1","unstructured":"Nitin Bhatia et al. 2010. Survey of nearest neighbor techniques. arXiv preprint arXiv:1007.0085 (2010)."},{"key":"e_1_2_1_4_1","unstructured":"Booking. [n.d.]. https:\/\/www.booking.com\/."},{"key":"e_1_2_1_5_1","first-page":"3","article-title":"Generating All Maximal Independent Sets on Trees in Lexicographic","volume":"76","author":"Chang Y. H.","year":"1994","unstructured":"Y. H. Chang, Jia-Shung Wang, and Richard C. T. Lee. 1994. Generating All Maximal Independent Sets on Trees in Lexicographic Order. Inf. Sci. 76, 3-4 (1994), 279--296.","journal-title":"Order. Inf. Sci."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"3966","DOI":"10.1109\/TKDE.2021.3137955","article-title":"Higher-order truss decomposition in graphs","volume":"35","author":"Chen Zi","year":"2021","unstructured":"Zi Chen, Long Yuan, Li Han, and Zhengping Qian. 2021. Higher-order truss decomposition in graphs. IEEE Transactions on Knowledge and Data Engineering 35, 4 (2021), 3966--3978.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcps.2014.08.002"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2595166.2595169"},{"key":"e_1_2_1_9_1","first-page":"865","article-title":"An efficient and scalable approach to CNN queries in a road network","volume":"2","author":"Cho Hyung-Ju","year":"2005","unstructured":"Hyung-Ju Cho and Chin-Wan Chung. 2005. An efficient and scalable approach to CNN queries in a road network. In PVLDB, Vol. 2. 865--876.","journal-title":"PVLDB"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"Graph Summarization: Compactness Meets Efficiency","volume":"2","author":"Chu Deming","year":"2024","unstructured":"Deming Chu, Fan Zhang, Wenjie Zhang, Ying Zhang, and Xuemin Lin. 2024. Graph Summarization: Compactness Meets Efficiency. Proceedings of the ACM on Management of Data 2, 3 (2024), 1--26.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_11_1","volume-title":"Efficient continuous nearest neighbor query in spatial networks using euclidean restriction","author":"Demiryurek Ugur","unstructured":"Ugur Demiryurek, Farnoush Banaei-Kashani, and Cyrus Shahabi. 2009. Efficient continuous nearest neighbor query in spatial networks using euclidean restriction. In Proceedings of SSTD. Springer, 25--43."},{"key":"e_1_2_1_12_1","first-page":"25","article-title":"Efficient Continuous Nearest Neighbor Query in Spatial Networks Using Euclidean Restriction","volume":"5644","author":"Demiryurek Ugur","year":"2009","unstructured":"Ugur Demiryurek, Farnoush Banaei Kashani, and Cyrus Shahabi. 2009. Efficient Continuous Nearest Neighbor Query in Spatial Networks Using Euclidean Restriction. In Proceedings of SSTD, Vol. 5644. 25--43.","journal-title":"Proceedings of SSTD"},{"key":"e_1_2_1_13_1","unstructured":"Dianping. [n.d.]. https:\/\/www.dianping.com\/."},{"key":"e_1_2_1_14_1","unstructured":"DiDi. [n.d.]. https:\/\/www.didiglobal.com."},{"key":"e_1_2_1_15_1","volume-title":"A note on two problems in connexion with graphs","author":"Dijkstra Edsger W.","unstructured":"Edsger W. Dijkstra. 1959. A note on two problems in connexion with graphs. Vol. 1. 269--271."},{"key":"e_1_2_1_16_1","volume-title":"Contraction hierarchies: Faster and simpler hierarchical routing in road networks","author":"Geisberger Robert","unstructured":"Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of WEA. Springer, 319--333."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of ICDE. IEEE, 1298--1309","author":"He Dan","year":"2019","unstructured":"Dan He, Sibo Wang, Xiaofang Zhou, and Reynold Cheng. 2019. An efficient framework for correctness-aware kNN queries on road networks. In Proceedings of ICDE. IEEE, 1298--1309."},{"key":"e_1_2_1_18_1","volume-title":"PRAGA: Prototype-aware Graph Adaptive Aggregation for Spatial Multi-modal Omics Analysis. arXiv preprint arXiv:2409.12728","author":"Huang Xinlei","year":"2024","unstructured":"Xinlei Huang, Zhiqi Ma, Dian Meng, Yanran Liu, Shiwei Ruan, Qingqiang Sun, Xubin Zheng, and Ziyue Qiao. 2024. PRAGA: Prototype-aware Graph Adaptive Aggregation for Spatial Multi-modal Omics Analysis. arXiv preprint arXiv:2409.12728 (2024)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.3390\/electronics12214536"},{"key":"e_1_2_1_20_1","first-page":"1","article-title":"Tree index nearest neighbor search of moving objects along a road network","volume":"2021","author":"Jiang Wei","year":"2021","unstructured":"Wei Jiang, Fangliang Wei, Guanyu Li, Mei Bai, Yongqiang Ren, and Jingmin An. 2021. Tree index nearest neighbor search of moving objects along a road network. Wireless Communications and Mobile Computing 2021 (2021), 1--18.","journal-title":"Wireless Communications and Mobile Computing"},{"key":"e_1_2_1_21_1","volume-title":"Kolahdouzan and Cyrus Shahabi","author":"Mohammad","year":"2004","unstructured":"Mohammad R. Kolahdouzan and Cyrus Shahabi. 2004. Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases. In PVLDB. 840--851."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-005-4575-8"},{"key":"e_1_2_1_23_1","volume-title":"ROAD: A new spatial object search framework for road networks","author":"Lee Ken CK","year":"2010","unstructured":"Ken CK Lee, Wang-Chien Lee, Baihua Zheng, and Yuan Tian. 2010. ROAD: A new spatial object search framework for road networks. IEEE transactions on knowledge and data engineering 24, 3 (2010), 547--560."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of ICDE. 881--892","author":"Li Chuanwen","year":"2018","unstructured":"Chuanwen Li, Yu Gu, Jianzhong Qi, Jiayuan He, Qingxu Deng, and Ge Yu. 2018. A GPU Accelerated Update Efficient Index for kNN Queries in Road Networks. In Proceedings of ICDE. 881--892."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00758-w"},{"key":"e_1_2_1_26_1","first-page":"594","article-title":"Toain: a throughput optimizing adaptive index for answering dynamic k nn queries on road networks","volume":"11","author":"Luo Siqiang","year":"2018","unstructured":"Siqiang Luo, Ben Kao, Guoliang Li, Jiafeng Hu, Reynold Cheng, and Yudian Zheng. 2018. Toain: a throughput optimizing adaptive index for answering dynamic k nn queries on road networks. PVLDB 11, 5 (2018), 594--606.","journal-title":"PVLDB"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3694966","article-title":"A survey of distributed graph algorithms on massive graphs","volume":"57","author":"Meng Lingkai","year":"2024","unstructured":"Lingkai Meng, Yu Shao, Long Yuan, Longbin Lai, Peng Cheng, Xue Li, Wenyuan Yu, Wenjie Zhang, Xuemin Lin, and Jingren Zhou. 2024. A survey of distributed graph algorithms on massive graphs. Comput. Surveys 57, 2 (2024), 1--39.","journal-title":"Comput. Surveys"},{"key":"e_1_2_1_28_1","volume-title":"Dimitris Papadias, and Nikos Mamoulis.","author":"Mouratidis Kyriakos","year":"2006","unstructured":"Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, and Nikos Mamoulis. 2006. Continuous Nearest Neighbor Monitoring in Road Networks. In PVLDB. 43--54."},{"key":"e_1_2_1_29_1","volume-title":"Algorithmic Aspects of Cloud Computing: Second International Workshop, ALGOCLOUD 2016","author":"Nodarakis Nikolaos","year":"2017","unstructured":"Nikolaos Nodarakis, Angeliki Rapti, Spyros Sioutas, Athanasios K Tsakalidis, Dimitrios Tsolis, Giannis Tzimas, and Yannis Panagis. 2017. (A) kNN query processing on the cloud: a survey. In Algorithmic Aspects of Cloud Computing: Second International Workshop, ALGOCLOUD 2016, Aarhus, Denmark, August 22, 2016, Revised Selected Papers 2. Springer, 26--40."},{"key":"e_1_2_1_30_1","unstructured":"OpenRice. [n.d.]. https:\/\/www.openrice.com\/."},{"key":"e_1_2_1_31_1","unstructured":"OpenTable. [n.d.]. https:\/\/www.opentable.com.au\/."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of SIGMOD. 709--724","author":"Ouyang Dian","year":"2018","unstructured":"Dian Ouyang, Lu Qin, Lijun Chang, Xuemin Lin, Ying Zhang, and Qing Zhu. 2018. When hierarchy meets 2-hop-labeling: Efficient shortest distance queries on road networks. In Proceedings of SIGMOD. 709--724."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of SIGMOD. 1781--1795","author":"Ouyang Dian","year":"2020","unstructured":"Dian Ouyang, Dong Wen, Lu Qin, Lijun Chang, Ying Zhang, and Xuemin Lin. 2020. Progressive top-k nearest neighbors search in large road networks. In Proceedings of SIGMOD. 1781--1795."},{"key":"e_1_2_1_34_1","volume-title":"Query processing in spatial network databases","author":"Papadias Dimitris","unstructured":"Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao. 2003. Query processing in spatial network databases. In PVLDB. Elsevier, 802--813."},{"key":"e_1_2_1_35_1","unstructured":"Frederick Muench Ph.D. 2010 November 1. The Burden of Choice. https:\/\/www.psychologytoday.com\/ca\/blog\/more-tech-support\/201011\/the-burden-choice."},{"key":"e_1_2_1_36_1","volume-title":"Holistic Memory Diversification for Incremental Learning in Growing Graphs. arXiv preprint arXiv:2406.07413","author":"Qiao Ziyue","year":"2024","unstructured":"Ziyue Qiao, Junren Xiao, Qingqiang Sun, Meng Xiao, and Hui Xiong. 2024. Holistic Memory Diversification for Incremental Learning in Growing Graphs. arXiv preprint arXiv:2406.07413 (2024)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_38_1","volume-title":"The paradox of choice: Why more is less. New York","author":"Schwartz Barry","year":"2004","unstructured":"Barry Schwartz. 2004. The paradox of choice: Why more is less. New York (2004)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025153016110"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of ICDE. IEEE, 609--620","author":"Shen Bilong","year":"2017","unstructured":"Bilong Shen, Ying Zhao, Guoliang Li, Weimin Zheng, Yue Qin, Bo Yuan, and Yongming Rao. 2017. V-tree: Efficient knn search on moving objects with road-network constraints. In Proceedings of ICDE. IEEE, 609--620."},{"key":"e_1_2_1_41_1","volume-title":"The more the merrier: Souvenir shopping, the absence of choice overload and preferred attributes. Tourism management perspectives 26","author":"Sthapit Erose","year":"2018","unstructured":"Erose Sthapit. 2018. The more the merrier: Souvenir shopping, the absence of choice overload and preferred attributes. Tourism management perspectives 26 (2018), 126--134."},{"key":"e_1_2_1_42_1","volume-title":"Interdependence-Adaptive Mutual Information Maximization for Graph Contrastive Learning","author":"Sun Qingqiang","year":"2024","unstructured":"Qingqiang Sun, Kai Wang, Wenjie Zhang, Peng Cheng, and Xuemin Lin. 2024. Interdependence-Adaptive Mutual Information Maximization for Graph Contrastive Learning. IEEE Transactions on Knowledge and Data Engineering (2024), 1--12."},{"key":"e_1_2_1_43_1","unstructured":"Trip. [n.d.]. https:\/\/www.trip.com\/."},{"key":"e_1_2_1_44_1","unstructured":"Alina Tugend. 2010 February 27. Too many choices: A problem that can paralyze. https:\/\/www.nytimes.com\/2010\/02\/27\/your-money\/27shortcuts.html?_r=1&."},{"key":"e_1_2_1_45_1","unstructured":"Uber. [n.d.]. https:\/\/www.uber.com\/."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3665844.3665853"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3626738","article-title":"Neural Attributed Community Search at Billion Scale","volume":"1","author":"Wang Jianwei","year":"2024","unstructured":"Jianwei Wang, Kai Wang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2024. Neural Attributed Community Search at Billion Scale. Proceedings of the ACM on Management of Data 1, 4 (2024), 1--25.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675042"},{"key":"e_1_2_1_49_1","first-page":"117","article-title":"Missing Data Imputation with Uncertainty-Driven Network","volume":"2","author":"Wang Jianwei","year":"2024","unstructured":"Jianwei Wang, Ying Zhang, Kai Wang, Xuemin Lin, and Wenjie Zhang. 2024. Missing Data Imputation with Uncertainty-Driven Network. Proceedings of the ACM on Management of Data 2, 3 (2024), 117.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of ICDE. IEEE, 2579--2592","author":"Wang Yiqi","year":"2023","unstructured":"Yiqi Wang, Long Yuan, Zi Chen, Wenjie Zhang, Xuemin Lin, and Qing Liu. 2023. Towards efficient shortest path counting on billion-scale graphs. In Proceedings of ICDE. IEEE, 2579--2592."},{"key":"e_1_2_1_51_1","unstructured":"Yiqi Wang Long Yuan Wenjie Zhang Xuemin Lin Zi Chen and Qing Liu. 2024. Technical Report. https:\/\/arxiv.org\/pdf\/2408.05432."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681997"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3648160.3648171"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSB.2005.9"},{"key":"e_1_2_1_55_1","unstructured":"Yelp. [n.d.]. https:\/\/www.yelp.com\/."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675049"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2783933"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494148"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of ICDE. IEEE Computer Society, 871--882","author":"Zheng Bolong","year":"2016","unstructured":"Bolong Zheng, Kai Zheng, Xiaokui Xiao, Han Su, Hongzhi Yin, Xiaofang Zhou, and GuoHui Li. 2016. Keyword-aware continuous kNN query on road networks. In Proceedings of ICDE. IEEE Computer Society, 871--882."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2399306"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3704965.3704975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T17:28:46Z","timestamp":1739899726000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3704965.3704975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9]]},"references-count":60,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["10.14778\/3704965.3704975"],"URL":"https:\/\/doi.org\/10.14778\/3704965.3704975","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,9]]},"assertion":[{"value":"2025-02-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}