{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T13:20:23Z","timestamp":1782739223592,"version":"3.54.5"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>\n            A\n            <jats:italic>k<\/jats:italic>\n            nearest neighbor (\n            <jats:italic>k<\/jats:italic>\n            NN) query on road networks retrieves the\n            <jats:italic>k<\/jats:italic>\n            closest points of interest (POIs) by their network distances from a given location. Today, in the era of ubiquitous mobile computing, this is a highly pertinent query. While Euclidean distance has been used as a heuristic to search for the closest POIs by their road network distance, its efficacy has not been thoroughly investigated. The most recent methods have shown significant improvement in query performance. Earlier studies, which proposed disk-based indexes, were compared to the current state-of-the-art in main memory. However, recent studies have shown that main memory comparisons can be challenging and require careful adaptation. This paper presents an extensive experimental investigation in main memory to settle these and several other issues. We use efficient and fair memory-resident implementations of each method to reproduce past experiments and conduct additional comparisons for several overlooked evaluations. Notably we revisit a previously discarded technique (IER) showing that, through a simple improvement, it is often the best performing technique.\n          <\/jats:p>","DOI":"10.14778\/2904121.2904125","type":"journal-article","created":{"date-parts":[[2016,4,12]],"date-time":"2016-04-12T12:24:41Z","timestamp":1460463881000},"page":"492-503","source":"Crossref","is-referenced-by-count":179,"title":["k-nearest neighbors on road networks"],"prefix":"10.14778","volume":"9","author":[{"given":"Tenindra","family":"Abeywickrama","sequence":"first","affiliation":[{"name":"Monash University, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Muhammad Aamir","family":"Cheema","sequence":"additional","affiliation":[{"name":"Monash University, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Taniar","sequence":"additional","affiliation":[{"name":"Monash University, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/www.globalwebindex.net\/blog\/top-global-smartphone-apps.  https:\/\/www.globalwebindex.net\/blog\/top-global-smartphone-apps."},{"key":"e_1_2_1_2_1","unstructured":"https:\/\/github.com\/tenindra\/RN-kNN-Exp.  https:\/\/github.com\/tenindra\/RN-kNN-Exp."},{"key":"e_1_2_1_3_1","unstructured":"http:\/\/www.dis.uniroma1.it\/%7Echallenge9\/.  http:\/\/www.dis.uniroma1.it\/%7Echallenge9\/."},{"key":"e_1_2_1_4_1","unstructured":"http:\/\/www.openstreetmap.org.  http:\/\/www.openstreetmap.org."},{"key":"e_1_2_1_5_1","unstructured":"http:\/\/www.cs.utah.edu\/%7Elifeifei\/SpatialDataset.htm.  http:\/\/www.cs.utah.edu\/%7Elifeifei\/SpatialDataset.htm."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904121.2904125"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790174.2790188"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791188.2791193"},{"key":"e_1_2_1_9_1","first-page":"865","volume-title":"VLDB","author":"Cho H.-J.","year":"2005","unstructured":"H.-J. Cho and C.-W. Chung . An efficient and scalable approach to cnn queries in a road network . In VLDB , pages 865 -- 876 , 2005 . H.-J. Cho and C.-W. Chung. An efficient and scalable approach to cnn queries in a road network. In VLDB, pages 865--876, 2005."},{"key":"e_1_2_1_10_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. Stein , R. L. Rivest , and C. E. Leiserson . Introduction to Algorithms . McGraw-Hill , 2 nd edition, 2001 . T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. McGraw-Hill, 2nd edition, 2001.","edition":"2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788912"},{"key":"e_1_2_1_12_1","volume-title":"SODA","author":"Goldberg A. V.","year":"2005","unstructured":"A. V. Goldberg and C. Harrelson . Computing the shortest path: A search meets graph theory . In SODA , 2005 . A. V. Goldberg and C. Harrelson. Computing the shortest path: A search meets graph theory. In SODA, 2005."},{"key":"e_1_2_1_13_1","first-page":"894","volume-title":"VLDB","author":"Hu H.","year":"2006","unstructured":"H. Hu , D. L. Lee , and V. C. S. Lee . Distance indexing on road networks . In VLDB , pages 894 -- 905 , 2006 . H. Hu, D. L. Lee, and V. C. S. Lee. Distance indexing on road networks. In VLDB, pages 894--905, 2006."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316762"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.243"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516476"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315520"},{"key":"e_1_2_1_19_1","volume-title":"Morgan Kaufmann","author":"Samet H.","year":"2005","unstructured":"H. Samet . Foundations of Multidimensional and Metric Data Structures . Morgan Kaufmann , 2005 . H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, 2005."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376623"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1097064.1097093"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735470"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140438"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2399306"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505749"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2904121.2904125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:54:46Z","timestamp":1672224886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2904121.2904125"}},"subtitle":["a journey in experimentation and in-memory implementation"],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.14778\/2904121.2904125"],"URL":"https:\/\/doi.org\/10.14778\/2904121.2904125","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}