{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T08:39:59Z","timestamp":1769935199185,"version":"3.49.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["PRP\/026\/21FX"],"award-info":[{"award-number":["PRP\/026\/21FX"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Due to the advancement of geo-positioning technology, the terrain data has become increasingly popular and has drawn a lot of research effort from both academia and industry. The distance computation on the terrain surface is a fundamental and important problem that is widely applied in geographical information systems and 3D modeling. As could be observed from the existing studies, online computation of the distance on the terrain surface is very expensive. All existing index-based methods are only efficient under the case where the distance query must be performed among a small set of predefined points-of-interest known apriori. But, in general cases, they could not scale up to sizable datasets due to their intolerable oracle building time and space consumption.<\/jats:p>\n          <jats:p>In this paper, we studied the arbitrary point-to-arbitrary point distance query on the terrain surface in which no assumption is imposed on the query points, and the distance query could be performed between any two arbitrary points. We propose an indexing structure, namely Efficient Arbitrary Point-to-Arbitrary Point Distance Oracle (EAR-Oracle), with theoretical guarantee on the accuracy, oracle building time, oracle size and query time. Our experiments demonstrate that our oracle enjoys excellent scalability and it scales up to enormous terrain surfaces but none of the existing index-based methods could be able to. Besides, it significantly outperforms all existing online computation methods by orders of magnitude in terms of the query time.<\/jats:p>","DOI":"10.1145\/3588694","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":5,"title":["EAR-Oracle: On Efficient Indexing for Distance Queries between Arbitrary Points on Terrain Surface"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9314-1096","authenticated-orcid":false,"given":"Bo","family":"Huang","sequence":"first","affiliation":[{"name":"Southern University of Science and Technology, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5548-7301","authenticated-orcid":false,"given":"Victor Junqiu","family":"Wei","sequence":"additional","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7045-6503","authenticated-orcid":false,"given":"Raymond Chi-Wing","family":"Wong","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8424-0092","authenticated-orcid":false,"given":"Bo","family":"Tang","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shenzhen, China"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"A. Al-Badarneh H. Najadat and A. Alraziqi. 2012. A classifier to detect tumor disease in MRI brain images. In The international conference series on Advances in Social Network Analysis and Mining (ASONAM). 784--787.","DOI":"10.1109\/ASONAM.2012.142"},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Lyudmil Aleksandrov Hristo N Djidjev Hua Guo Anil Maheshwari Doron Nussbaum and J\u00f6rg-R\u00fcdiger Sack. 2010. Algorithms for approximate shortest path queries on weighted polyhedral surfaces. In Discrete & Computational Geometry. 762--801.","DOI":"10.1007\/s00454-009-9204-0"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Lyudmil Aleksandrov Hristo N Djidjev Hua Guo Anil Maheshwari Doron Nussbaum and J\u00f6rg-R\u00fcdiger Sack. 2010. Algorithms for approximate shortest path queries on weighted polyhedral surfaces. In Discrete & Computational Geometry. 762--801.","DOI":"10.1007\/s00454-009-9204-0"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044733"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Marcel Campen Martin Heistermann and Leif Kobbelt. 2013. Practical Anisotropic Geodesy. Comput. Graph. Forum 63--71.","DOI":"10.1111\/cgf.12173"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5194\/egusphere-egu21-14039"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98601"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.2312\/LocalChapterEvents"},{"key":"e_1_2_2_10_1","volume-title":"A Survey of Algorithms for Geodesic Paths and Distances. arXiv preprint arXiv:2007.10430","author":"Crane Keenan","year":"2020","unstructured":"Keenan Crane, Marco Livesu, Enrico Puppo, and Yipeng Qin. 2020. A Survey of Algorithms for Geodesic Paths and Distances. arXiv preprint arXiv:2007.10430 (2020)."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.152"},{"key":"e_1_2_2_12_1","volume-title":"International Conference on Web and Wireless Geographical Information Systems (WWGIS). 151--166","author":"Deng Ke","year":"2004","unstructured":"Ke Deng and Xiaofang Zhou. 2004. Expansion-based algorithms for finding single pair shortest path on surface. In International Conference on Web and Wireless Geographical Information Systems (WWGIS). 151--166."},{"key":"e_1_2_2_13_1","volume-title":"Qing Liu, Kai Xu, and Xuemin Lin.","author":"Deng Ke","year":"2008","unstructured":"Ke Deng, Xiaofang Zhou, Heng Tao Shen, Qing Liu, Kai Xu, and Xuemin Lin. 2008. A multi-resolution surface distance model for k-NN query processing. ACM International Journal on Very Large Data Bases (VLDBJ), 1101--1119."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-7998.2006.00215.x"},{"key":"e_1_2_2_15_1","volume-title":"The European Symposium on Algorithms (ESA). 579--590","author":"Djidjev Hristo N","year":"2011","unstructured":"Hristo N Djidjev and Christian Sommer. 2011. Approximate distance queries forweighted polyhedral surfaces. In The European Symposium on Algorithms (ESA). 579--590."},{"key":"e_1_2_2_16_1","unstructured":"Robert Geisberger Peter Sanders Dominik Schultes and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Experimental Algorithms."},{"key":"e_1_2_2_17_1","volume-title":"Exact routing in large road networks using contraction hierarchies. Transportation Science","author":"Geisberger Robert","year":"2012","unstructured":"Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks using contraction hierarchies. Transportation Science (2012)."},{"key":"e_1_2_2_18_1","volume-title":"Co-location Pattern Discovery","author":"Wei Hu.","unstructured":"Wei Hu. 2008. Co-location Pattern Discovery. Springer US, 98--103."},{"key":"e_1_2_2_19_1","volume-title":"Raymond Chi-Wing Wong, and Bo Tang.","author":"Huang Bo","year":"2022","unstructured":"Bo Huang, Victor Junqiu Wei, Raymond Chi-Wing Wong, and Bo Tang. 2022. On Efficient Indexing for Distance Queries between Arbitrary Points on Terrain Surface (Technical Report). https:\/\/github.com\/ ItakEjgo\/weighted_distance_oracle\/tree\/master\/technicalreport"},{"key":"e_1_2_2_20_1","volume-title":"Functional magnetic resonance imaging","author":"Huettel S. A.","unstructured":"S. A. Huettel, A. W. Song, and G. McCarthy. 2004. Functional magnetic resonance imaging. In Sinauer Associates."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/GMAP.2000.838256"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850591"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732226"},{"key":"e_1_2_2_24_1","unstructured":"Stephen Kiazyk S\u00e9bastien Loriot and \u00c9ric Colin de Verdi\u00e8re. 2021. Triangulated Surface Mesh Shortest Paths. In CGAL User and Reference Manual. CGAL Editorial Board. https:\/\/doc.cgal.org\/5.3\/Manual\/packages.html# PkgSurfaceMeshShortestPath"},{"key":"e_1_2_2_25_1","unstructured":"M. Kortgen G. J. Park M. Novotni and R. Klei. 2003. 3D shape matching with 3D shape contexts. In Central European Seminar on Computer Graphics (CESCG). 5--17."},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Mark Lanthier Anil Maheshwari and J-R Sack. 2001. Approximating shortest paths on weighted polyhedral surfaces. Algorithmica 527--562.","DOI":"10.1007\/s00453-001-0027-5"},{"key":"e_1_2_2_27_1","volume-title":"When Creators Meet the Metaverse: A Survey on Computational Arts. ArXiv abs\/2111","author":"Lee Lik-Hang","year":"2021","unstructured":"Lik-Hang Lee, Zijun Lin, Rui Hu, Zhengya Gong, Abhishek Kumar, Tangyao Li, Sijia Li, and Pan Hui. 2021. When Creators Meet the Metaverse: A Survey on Computational Arts. ArXiv abs\/2111.13486 (2021). https:\/\/arxiv.org\/abs\/2111.13486"},{"key":"e_1_2_2_28_1","volume-title":"Virtual Ecosystem, and Research Agenda. ArXiv abs\/2110.05352","author":"Lee Lik-Hang","year":"2021","unstructured":"Lik-Hang Lee, Tristan Braud, Pengyuan Zhou, Lin Wang, Dianlei Xu, Zijun Lin, Abhishek Kumar, Carlos Bermejo, and Pan Hui. 2021. All One Needs to Know about Metaverse: A Complete Survey on Technological Singularity, Virtual Ecosystem, and Research Agenda. ArXiv abs\/2110.05352 (2021)."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989369"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Anders M\u00e5rell John P Ball and Annika Hofgaard. 2002. Foraging and movement paths of female reindeer: insights from fractal analysis correlated random walks and L\u00e9vy flights. Canadian Journal of Zoology 854--865.","DOI":"10.1139\/z02-061"},{"key":"e_1_2_2_31_1","series-title":"SIAM J. Comput., 647--668","volume-title":"The discrete geodesic problem","author":"Mitchell Joseph SB","unstructured":"Joseph SB Mitchell, David M Mount, and Christos H Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput., 647--668."},{"key":"e_1_2_2_32_1","volume-title":"International Journal for Advance Research and Development","author":"Oo Zaw Lin","year":"2020","unstructured":"Zaw Lin Oo and Mya Sandar Kyin. 2020. Discovery and comparative study on spatial co-location and association rule mining of spatial data mining. International Journal for Advance Research and Development (2020), 16--19."},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"L Tiina Sarjakoski Pyry Kettunen Hanna-Marika Flink Mari Laakso Mikko R\u00f6nneberg and Tapani Sarjakoski. 2012. Analysis of verbal route descriptions and landmarks for hiking. Personal and Ubiquitous Computing 1001--1011.","DOI":"10.1007\/s00779-011-0460-7"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453966"},{"key":"e_1_2_2_35_1","volume-title":"European Conference on Computer Vision (ECCV). 1--15","author":"Shotton J.","unstructured":"J. Shotton, J. Winn, C. Rother, and A. Criminisi. 2006. Textonboost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation. In European Conference on Computer Vision (ECCV). 1--15."},{"key":"e_1_2_2_36_1","series-title":"Handbook of Approximation Algorithms and Metaheuristics","volume-title":"Contemporary and Emerging Applications","author":"Smid Michiel H. M.","unstructured":"Michiel H. M. Smid. 2018. The Well-Separated Pair Decomposition and Its Applications. In Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 2: Contemporary and Emerging Applications, Chapter 4. Chapman and Hall\/CRC."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","unstructured":"United States Geological Survey. 2021. 3D Elevation Program 1 arc-second Digital Elevation Model. In United States Geological Survey. Distributed by OpenTopography. https:\/\/doi.org\/10.5069\/G98K778D","DOI":"10.5069\/G98K778D"},{"key":"e_1_2_2_38_1","volume-title":"CGAL User and Reference Manual","author":"Project The CGAL","unstructured":"The CGAL Project. 2021. CGAL User and Reference Manual. CGAL Editorial Board. https:\/\/doc.cgal.org\/5.3\/ Manual\/packages.html"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397536.3422216"},{"key":"e_1_2_2_40_1","volume-title":"Impacts of spatial clustering of urban land cover on land surface temperature across K\u00f6ppen climate zones in the contiguous United States. Landscape and urban planning 192","author":"Wang Chuyuan","year":"2019","unstructured":"Chuyuan Wang, Yubin Li, Soe W Myint, Qunshan Zhao, and Elizabeth A Wentz. 2019. Impacts of spatial clustering of urban land cover on land surface temperature across K\u00f6ppen climate zones in the contiguous United States. Landscape and urban planning 192 (2019), 103668."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563773"},{"key":"e_1_2_2_42_1","volume-title":"Distance Oracle on Terrain Surface. In ACM Conference on Management of Data (SIGMOD). 1211--1226","author":"Wei Victor Junqiu","unstructured":"Victor Junqiu Wei, Raymond Chi-Wing Wong, Cheng Long, and David M. Mount. 2017. Distance Oracle on Terrain Surface. In ACM Conference on Management of Data (SIGMOD). 1211--1226."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_2_2_44_1","volume-title":"ACM International Conference on Very Large Data Bases (VLDB). 1114--1125","author":"Xing S.","unstructured":"S. Xing, C. Shahabi, and B. Pan. 2009. Continuous monitoring of nearest neighbors on land surface. In ACM International Conference on Very Large Data Bases (VLDB). 1114--1125."},{"key":"e_1_2_2_45_1","volume-title":"The Conference on Information and Knowledge Management (CIKM). 942--951","author":"Yan D.","unstructured":"D. Yan, Z. Zhao, and W. Ng. 2012. Monochromatic and bichromatic reverse nearest neighbor queries on land surfaces. In The Conference on Information and Knowledge Management (CIKM). 942--951."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588694","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:13Z","timestamp":1750178833000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588694"],"URL":"https:\/\/doi.org\/10.1145\/3588694","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}