{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T07:36:31Z","timestamp":1769931391171,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T00:00:00Z","timestamp":1671148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004377","name":"Hong Kong Polytechnic University","doi-asserted-by":"crossref","award":["P0039657"],"award-info":[{"award-number":["P0039657"]}],"id":[{"id":"10.13039\/501100004377","id-type":"DOI","asserted-by":"crossref"}]},{"name":"HKUST","award":["PRP\/026\/21FX"],"award-info":[{"award-number":["PRP\/026\/21FX"]}]},{"name":"Ministry of Education, Singapore, under its Academic Research Fund","award":["MOE-T2EP20220-0011 and MOE-T2EP20221-0013"],"award-info":[{"award-number":["MOE-T2EP20220-0011 and MOE-T2EP20221-0013"]}]},{"name":"NSF","award":["CCF-1618866, IIS-18-16889, IIS-20-41415, and IIS-21-14451"],"award-info":[{"award-number":["CCF-1618866, IIS-18-16889, IIS-20-41415, and IIS-21-14451"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>Due to the advance of the geo-spatial positioning and the computer graphics technology, digital terrain data has become increasingly popular nowadays. Query processing on terrain data has attracted considerable attention from both the academic and the industry communities.<\/jats:p>\n          <jats:p>\n            Proximity queries such as the shortest path\/distance query,\n            <jats:italic>k<\/jats:italic>\n            nearest\/farthest neighbor query, and top-\n            <jats:italic>k<\/jats:italic>\n            closest\/farthest pairs query are fundamental and important queries in the context of the terrain surfaces, and they have a lot of applications in Geographical Information System, 3D object feature vector construction, and 3D object data mining. In this article, we first study the most fundamental type of query, namely, shortest distance and path query, which is to find the shortest distance and path between two points of interest on the surface of the terrain. As observed by existing studies, computing the exact shortest distance\/path is very expensive. Some existing studies proposed\n            <jats:italic>\u03f5<\/jats:italic>\n            -approximate distance and path oracles, where\n            <jats:italic>\u03f5<\/jats:italic>\n            is a non-negative real-valued error parameter. However, the best-known algorithm has a large oracle construction time, a large oracle size, and a large query time. Motivated by this, we propose a novel\n            <jats:italic>\u03f5<\/jats:italic>\n            -approximate distance and path oracle called the\n            <jats:italic>\n              <jats:underline>S<\/jats:underline>\n              pace\n              <jats:underline>E<\/jats:underline>\n              fficient distance and path oracle (SE),\n            <\/jats:italic>\n            which has a small oracle construction time, a small oracle size, and a small distance and path query time, thanks to its compactness of storing concise information about pairwise distances between any two points-of-interest. Then, we propose several algorithms for the\n            <jats:italic>k<\/jats:italic>\n            nearest\/farthest neighbor and top-\n            <jats:italic>k<\/jats:italic>\n            closest\/farthest pairs queries with the assistance of our distance and path oracle\n            <jats:italic>SE<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Our experimental results show that the oracle construction time, the oracle size, and the distance and path query time of\n            <jats:italic>SE<\/jats:italic>\n            are up to two, three, and five orders of magnitude faster than the best-known algorithm, respectively. Besides, our algorithms for other proximity queries including\n            <jats:italic>k<\/jats:italic>\n            nearest\/farthest neighbor queries and top-\n            <jats:italic>k<\/jats:italic>\n            closest\/farthest pairs queries significantly outperform the state-of-the-art algorithms by up to two orders of magnitude.\n          <\/jats:p>","DOI":"10.1145\/3563773","type":"journal-article","created":{"date-parts":[[2022,9,16]],"date-time":"2022-09-16T09:29:34Z","timestamp":1663320574000},"page":"1-59","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Proximity Queries on Terrain Surface"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5548-7301","authenticated-orcid":false,"given":"Victor Junqiu","family":"Wei","sequence":"first","affiliation":[{"name":"Hong Kong Polytechnic University, Kowloon, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7045-6503","authenticated-orcid":false,"given":"Raymond Chi-Wing","family":"Wong","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Kowloon, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6806-8405","authenticated-orcid":false,"given":"Cheng","family":"Long","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, SG"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3290-8932","authenticated-orcid":false,"given":"David","family":"Mount","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8230-0653","authenticated-orcid":false,"given":"Hanan","family":"Samet","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,16]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"ASONAM","author":"Al-Badarneh A.","year":"2012","unstructured":"A. Al-Badarneh, H. Najadat, and A. Alraziqi. 2012. A classifier to detect tumor disease in MRI brain images. In ASONAM."},{"key":"e_1_3_3_3_2","volume-title":"Discrete & Computational Geometry","author":"Aleksandrov Lyudmil","year":"2010","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. Springer."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9204-0"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044733"},{"key":"e_1_3_3_6_2","volume-title":"ICML","author":"Beygelzimer Alina","year":"2006","unstructured":"Alina Beygelzimer, Sham Kakade, and John Langford. 2006. Cover trees for nearest neighbor. In ICML."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_3_3_8_2","volume-title":"SOCG","author":"Chen Jindong","year":"1990","unstructured":"Jindong Chen and Yijie Han. 1990. Shortest paths on a polyhedron. In SOCG."},{"key":"e_1_3_3_9_2","volume-title":"Introduction to Algorithms (3rd ed.)","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335414"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2003.08.007"},{"key":"e_1_3_3_12_2","volume-title":"ICDE","author":"Deng Ke","year":"2006","unstructured":"Ke Deng, Heng Tao Shen, Kai Xu, and Xuemin Lin. 2006. Surface k-NN query processing. In ICDE."},{"key":"e_1_3_3_13_2","volume-title":"WWGIS","author":"Deng Ke","year":"2005","unstructured":"Ke Deng and Xiaofang Zhou. 2005. Expansion-based algorithms for finding single pair shortest path on surface. In WWGIS."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0053-2"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-7998.2006.00215.x"},{"key":"e_1_3_3_16_2","volume-title":"ESA","author":"Djidjev Hristo N.","year":"2011","unstructured":"Hristo N. Djidjev and Christian Sommer. 2011. Approximate distance queries for weighted polyhedral surfaces. In ESA."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.09.016"},{"key":"e_1_3_3_18_2","volume-title":"CCCG","author":"Fischer John","year":"2005","unstructured":"John Fischer and Sariel Har-Peled. 2005. Dynamic well-separated pair decomposition made easy. In CCCG."},{"key":"e_1_3_3_19_2","first-page":"401","article-title":"The densest packing of 12 congruent circles in a circle","volume":"41","author":"Fodor Ferenc","year":"2000","unstructured":"Ferenc Fodor. 2000. The densest packing of 12 congruent circles in a circle. Beitr\u00e4ge Algebra Geom. 41 (2000), 401\u2013409.","journal-title":"Beitr\u00e4ge Algebra Geom."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2015.06.010"},{"key":"e_1_3_3_21_2","volume-title":"Sinauer Associates","author":"Huettel S. A.","year":"2004","unstructured":"S. A. Huettel, A. W. Song, and G. McCarthy. 2004. Functional magnetic resonance imaging. In Sinauer Associates."},{"key":"e_1_3_3_22_2","volume-title":"CVPR","author":"Jia Jiaya","year":"2003","unstructured":"Jiaya Jia and Chi-Keung Tang. 2003. Image repairing: Robust image synthesis by adaptive ND tensor voting. In CVPR. IEEE."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.20"},{"key":"e_1_3_3_24_2","volume-title":"GMPTA","author":"Kanai Takashi","year":"2000","unstructured":"Takashi Kanai and Hiromasa Suzuki. 2000. Approximate shortest path on a polyhedral surface based on selective refinement of the discrete graph and its applications. In GMPTA."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850591"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732226"},{"key":"e_1_3_3_27_2","volume-title":"NIPS","author":"K\u00e9gl Bal\u00e1zs","year":"2002","unstructured":"Bal\u00e1zs K\u00e9gl. 2002. Intrinsic dimension estimation using packing numbers. In NIPS."},{"key":"e_1_3_3_28_2","volume-title":"CESCG","author":"Kortgen M.","year":"2003","unstructured":"M. Kortgen, G. J. Park, M. Novotni, and R. Klei. 2003. 3D shape matching with 3D shape contexts. In CESCG."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20134"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/931222"},{"key":"e_1_3_3_31_2","volume-title":"SIGMOD","author":"Liu Lian","year":"2011","unstructured":"Lian Liu and Raymond Chi-Wing Wong. 2011. Finding shortest path on land surface. In SIGMOD."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1139\/z02-061"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_3_3_34_2","unstructured":"J. Sankaranarayanan H. Alborzi and H. Samet.Distance join queries on spatial networks. In ACM-GIS."},{"key":"e_1_3_3_35_2","unstructured":"J. Sankaranarayanan and H. Samet.Distance oracles for spatial networks. In ICDE."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.75"},{"key":"e_1_3_3_37_2","article-title":"Roads belong in databases.","author":"Sankaranarayanan Jagan","unstructured":"Jagan Sankaranarayanan and Hanan Samet. Roads belong in databases.IEEE Data Eng. Bull. 33, 2 (2010), 4\u201311.","journal-title":"IEEE Data Eng. Bull. 33, 2 (2010), 4\u201311."},{"key":"e_1_3_3_38_2","article-title":"Path oracles for spatial networks.","author":"Sankaranarayanan J.","unstructured":"J. Sankaranarayanan, H. Samet, and H. Alborzi. 2009.Path oracles for spatial networks.PVLDB 2, 1 (2009), 1210\u20131221","journal-title":"PVLDB 2, 1 (2009), 1210\u20131221"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00779-011-0460-7"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453966"},{"key":"e_1_3_3_41_2","volume-title":"ECCV","author":"Shotton J.","year":"2006","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 ECCV."},{"key":"e_1_3_3_42_2","volume-title":"ICDE","author":"Tauheed F.","year":"2012","unstructured":"F. Tauheed, L. Biveinis, T. Heinis, F. Schurmann, H. Markram, and A. Ailamaki. 2012. Accelerating range queries for brain simulations. In ICDE."},{"key":"e_1_3_3_43_2","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1145\/3397536.3422216","volume-title":"SIGSPATIAL","author":"Tran Nguyet","year":"2020","unstructured":"Nguyet Tran, Michael J. Dinneen, and Simone Linz. 2020. Close weighted shortest paths on 3D terrain surfaces. In SIGSPATIAL. 597\u2013607."},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906061161"},{"key":"e_1_3_3_45_2","volume-title":"SIGMOD","author":"Wei Victor Junqiu","year":"2017","unstructured":"Victor Junqiu Wei, Raymond Chi-Wing Wong, Cheng Long, and David M. Mount. 2017. Distance oracle on terrain surface. In SIGMOD."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_3_3_47_2","volume-title":"VLDB","author":"Xing S.","year":"2009","unstructured":"S. Xing, C. Shahabi, and B. Pan. 2009. Continuous monitoring of nearest neighbors on land surface. In VLDB."},{"key":"e_1_3_3_48_2","volume-title":"CIKM","author":"Yan D.","year":"2012","unstructured":"D. Yan, Z. Zhao, and W. Ng. 2012. Monochromatic and bichromatic reverse nearest neighbor queries on land surfaces. In CIKM."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476319"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563773","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563773","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:07Z","timestamp":1750186807000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,16]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3563773"],"URL":"https:\/\/doi.org\/10.1145\/3563773","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,16]]},"assertion":[{"value":"2021-10-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}