{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T22:01:30Z","timestamp":1782770490016,"version":"3.54.5"},"reference-count":37,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T00:00:00Z","timestamp":1704844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Using spatial data in mobile applications has grown significantly, thereby empowering users to explore locations, navigate unfamiliar areas, find transportation routes, employ geomarketing strategies, and model environmental factors. Spatial databases are pivotal in efficiently storing, retrieving, and manipulating spatial data to fulfill users\u2019 needs. Two fundamental spatial query types, k-nearest neighbors (kNN) and range search, enable users to access specific points of interest (POIs) based on their location, which are measured by actual road distance. However, retrieving the nearest POIs using actual road distance can be computationally intensive due to the need to find the shortest distance. Using straight-line measurements could expedite the process but might compromise accuracy. Consequently, this study aims to evaluate the accuracy of the Euclidean distance method in POIs retrieval by comparing it with the road network distance method. The primary focus is determining whether the trade-off between computational time and accuracy is justified, thus employing the Open Source Routing Machine (OSRM) for distance extraction. The assessment encompasses diverse scenarios and analyses factors influencing the accuracy of the Euclidean distance method. The methodology employs a quantitative approach, thereby categorizing query points based on density and analyzing them using kNN and range query methods. Accuracy in the Euclidean distance method is evaluated against the road network distance method. The results demonstrate peak accuracy for kNN queries at k=1, thus exceeding 85% across classes but declining as k increases. Range queries show varied accuracy based on POI density, with higher-density classes exhibiting earlier accuracy increases. Notably, datasets with fewer POIs exhibit unexpectedly higher accuracy, thereby providing valuable insights into spatial query processing.<\/jats:p>","DOI":"10.3390\/a17010029","type":"journal-article","created":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T07:50:48Z","timestamp":1704873048000},"page":"29","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Navigating the Maps: Euclidean vs. Road Network Distances in Spatial Queries"],"prefix":"10.3390","volume":"17","author":[{"given":"Pornrawee","family":"Tatit","sequence":"first","affiliation":[{"name":"Faculty of Information Technology, Monash University, Melbourne, VIC 3800, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5884-1409","authenticated-orcid":false,"given":"Kiki","family":"Adhinugraha","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Technology, La Trobe University, Melbourne, VIC 3086, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8862-3960","authenticated-orcid":false,"given":"David","family":"Taniar","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, Monash University, Melbourne, VIC 3800, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,1,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Brakatsoulas, S., Pfoser, D., and Theodoridis, Y. (2002, January 8\u201311). Revisiting R-tree construction principles. Proceedings of the East European Conference on Advances in Databases and Information Systems, Bratislava, Slovakia.","DOI":"10.1007\/3-540-45710-0_13"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1109\/12.663776","article-title":"A note on the complexity of Dijkstra\u2019s algorithm for graphs with weighted vertices","volume":"47","author":"Barbehenn","year":"1998","journal-title":"IEEE Trans. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"105197","DOI":"10.1016\/j.cor.2020.105197","article-title":"Vehicle routing on road networks: How good is Euclidean approximation?","volume":"129","author":"Dang","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Abeywickrama, T., Cheema, M.A., and Taniar, D. (2016). K-nearest neighbors on road networks: A journey in experimentation and in-memory implementation. arXiv.","DOI":"10.14778\/2904121.2904125"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1328911.1328920","article-title":"The priority r-tree: A practically efficient and worst-case optimal r-tree","volume":"4","author":"Arge","year":"2008","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Roussopoulos, N., Kelley, S., and Vincent, F. (1995, January 22\u201325). Nearest neighbor queries. Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, CA, USA.","DOI":"10.1145\/223784.223794"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1016\/j.jcss.2013.01.017","article-title":"A taxonomy for nearest neighbour queries in spatial databases","volume":"79","author":"Taniar","year":"2013","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1109\/T-C.1975.224297","article-title":"A Branch and Bound Algorithm for Computing k-Nearest Neighbors","volume":"24","author":"Fukunaga","year":"1975","journal-title":"IEEE Trans. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1145\/321296.321300","article-title":"Backtrack programming","volume":"12","author":"Golomb","year":"1965","journal-title":"J. ACM"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1287\/opre.14.4.699","article-title":"Branch-and-bound methods: A survey","volume":"14","author":"Lawler","year":"1966","journal-title":"Oper. Res."},{"key":"ref_11","unstructured":"Nilsson, N.J. (1971). Problem-Solving Methods in Artificial Intelligence, McGraw-Hill Book Company."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1145\/1071610.1071616","article-title":"Aggregate nearest neighbor queries in spatial databases","volume":"30","author":"Papadias","year":"2005","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"ref_13","unstructured":"Stanoi, I., Agrawal, D., and El Abbadi, A. (2000, January 14\u201315). Reverse nearest neighbor queries for dynamic databases. Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, Dallas, TX, USA."},{"key":"ref_14","unstructured":"Papadias, D., Shen, Q., Tao, Y., and Mouratidis, K. (April, January 30). Group nearest neighbor queries. Proceedings of the 20th International Conference on Data Engineering, Boston, MA, USA."},{"key":"ref_15","first-page":"71","article-title":"Multidimensional Range Search in Dynamically Balanced Trees","volume":"2","author":"Tropf","year":"1981","journal-title":"Angew. Info"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1508","DOI":"10.1016\/j.jcss.2014.12.025","article-title":"A taxonomy for region queries in spatial databases","volume":"81","author":"Taniar","year":"2015","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Xuan, K., Zhao, G., Taniar, D., and Srinivasan, B. (2008, January 8\u201310). Continuous range search query processing in mobile navigation. Proceedings of the 2008 14th IEEE International Conference on Parallel and Distributed Systems, Melbourne, VIC, Australia.","DOI":"10.1109\/ICPADS.2008.69"},{"key":"ref_18","unstructured":"Pfoser, D., Jensen, C.S., and Theodoridis, Y. (2000, January 10\u201314). Novel approaches to the indexing of moving object trajectories. Proceedings of the Very Large Data Bases (VLDB), Cairo, Egypt."},{"key":"ref_19","unstructured":"Freytag, J.-C., Lockemann, P., Abiteboul, S., Carey, M., Selinger, P., and Heuer, A. (2003, January 9\u201312). Query Processing in Spatial Network Databases. Proceedings of the 2003 VLDB Conference, Berlin, Germany."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Samet, H., Sankaranarayanan, J., and Alborzi, H. (2008, January 10\u201312). Scalable network distance browsing in spatial databases. Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, Vancouver, BC, Canada.","DOI":"10.1145\/1376616.1376623"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1109\/TKDE.2010.243","article-title":"ROAD: A new spatial object search framework for road networks","volume":"24","author":"Lee","year":"2010","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Lee, K.C., Lee, W.C., and Zheng, B. (2009, January 24\u201326). Fast object search on road networks. Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, St. Petersburg, Russia.","DOI":"10.1145\/1516360.1516476"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2175","DOI":"10.1109\/TKDE.2015.2399306","article-title":"G-tree: An efficient and scalable index for spatial search on road networks","volume":"27","author":"Zhong","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_24","unstructured":"Zhong, R., Li, G., Tan, K.L., and Zhou, L. (November, January 27). G-tree: An efficient index for knn search on road networks. Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, San Francisco, CA, USA."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Shahabi, C., Kolahdouzan, M.R., and Sharifzadeh, M. (2002, January 8\u20139). A road network embedding technique for k-nearest neighbor search in moving object databases. Proceedings of the 10th ACM International Symposium on Advances in Geographic Information Systems, Washington, DC, USA.","DOI":"10.1145\/585147.585167"},{"key":"ref_26","unstructured":"Kolahdouzan, M., and Shahabi, C. (September, January 31). Voronoi-based k nearest neighbor search for spatial network databases. Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, ON, Canada."},{"key":"ref_27","unstructured":"Mouratidis, K., Yiu, M.L., Papadias, D., and Mamoulis, N. (2006, January 12\u201315). Continuous nearest neighbor monitoring in road networks. Proceedings of the Very Large Data Bases (VLDB) Endowment, Seoul, Republic of Korea."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1016\/j.trpro.2014.10.066","article-title":"Analysis of the difference between the euclidean distance and the actual road distance in Brazil","volume":"3","year":"2014","journal-title":"Transp. Res. Procedia"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Hua, H., Xie, H., and Tanin, E. (2018, January 6\u20137). Is euclidean distance really that bad with road networks?. Proceedings of the 11th ACM SIGSPATIAL International Workshop on Computational Transportation Science, Seattle, WA, USA.","DOI":"10.1145\/3283207.3283215"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/cpe.2844","article-title":"Hilbert-order based spatial cloaking algorithm in road network","volume":"25","author":"Kim","year":"2013","journal-title":"Concurr. Comput. Pract. Exp."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Xiao, F., Tong, L., and Luo, S. (2019). A method for road network extraction from high-resolution SAR imagery using direction grouping and curve fitting. Remote Sens., 11.","DOI":"10.3390\/rs11232733"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Arbelaez, A., Mehta, D., O\u2019Sullivan, B., Quesada, L., and Sasmaz, A. (2017, January 2\u20136). Generation of a reference network for Ireland and its contribution to the design of an optical network architecture. Proceedings of the 2017 19th International Conference on Transparent Optical Networks (ICTON), Girona, Spain.","DOI":"10.1109\/ICTON.2017.8025124"},{"key":"ref_33","unstructured":"(2023, March 07). Geocoded National Address File (G-NAF), Available online: https:\/\/data.gov.au\/data\/dataset\/geocoded-national-address-file-g-naf."},{"key":"ref_34","unstructured":"(2023, March 07). Australian Statistical Geography Standard (ASGS). (July 2021\u2013June 2026) Edition 3, Available online: https:\/\/www.abs.gov.au\/statistics\/standards\/australian-statistical-geography-standard-asgs-edition-3\/latest-release."},{"key":"ref_35","first-page":"271","article-title":"Access to healthcare: A field survey in Istanbul","volume":"11","year":"2014","journal-title":"Z ITU J. Fac. Archit."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1023\/A:1022452311911","article-title":"Distance as a predominant factor in the utilisation of health services in the Kumasi metropolis, Ghana","volume":"56","author":"Buor","year":"2002","journal-title":"GeoJournal"},{"key":"ref_37","first-page":"15","article-title":"Measuring Geographical Accessibility to Healthcare Facilities in Peri-Urban Dwellers of Mbeya City, Tanzania","volume":"1","author":"Ngowi","year":"2021","journal-title":"MUST J. Res. Dev."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/1\/29\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T13:43:50Z","timestamp":1760103830000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/1\/29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,10]]},"references-count":37,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,1]]}},"alternative-id":["a17010029"],"URL":"https:\/\/doi.org\/10.3390\/a17010029","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,10]]}}}