{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T15:04:42Z","timestamp":1770131082696,"version":"3.49.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>\n                    The prevalence of computer graphics technology boosts the development of point clouds, which offer advantages over\n                    <jats:italic toggle=\"yes\">\n                      <jats:underline>T<\/jats:underline>\n                      riangular\n                      <jats:underline>I<\/jats:underline>\n                      rregular\n                      <jats:underline>N<\/jats:underline>\n                      etworks\n                    <\/jats:italic>\n                    , i.e.,\n                    <jats:italic toggle=\"yes\">TIN<\/jats:italic>\n                    s, in proximity queries. All existing on-the-fly shortest path query algorithms and oracles on a\n                    <jats:italic toggle=\"yes\">TIN<\/jats:italic>\n                    are expensive, and no algorithms can answer shortest path queries on a point cloud directly. Thus, we propose two types of efficient shortest path oracles on a point cloud. They answer the shortest path query between (1) a pair of\n                    <jats:italic toggle=\"yes\">\n                      <jats:underline>P<\/jats:underline>\n                      oints-\n                      <jats:underline>O<\/jats:underline>\n                      f-\n                      <jats:underline>I<\/jats:underline>\n                      nterests\n                    <\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">POIs<\/jats:italic>\n                    ), and (2) any point and a POI, respectively. We propose four adaptations of them to answer the query between any point and a POI (or any point if no POIs are given). We also propose two efficient proximity query algorithms using these oracles. Our two oracles and their proximity query algorithms outperform the best-known adapted oracle by 12 to 42,000 times in terms of the oracle construction time, oracle size and proximity query time, respectively\n                    <jats:xref ref-type=\"fn\">\n                      <jats:sup>1<\/jats:sup>\n                    <\/jats:xref>\n                    .\n                  <\/jats:p>","DOI":"10.1145\/3770577","type":"journal-article","created":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T09:08:16Z","timestamp":1759396096000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Path Oracles for Proximity Queries on Point Clouds"],"prefix":"10.1145","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6261-1569","authenticated-orcid":false,"given":"Yinzhao","family":"Yan","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, The Hong Kong University of Science and Technology","place":["Hong Kong, Hong Kong"]}],"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":"Department of Computer Science and Engineering, The Hong Kong University of Science and Technology","place":["Hong Kong, Hong Kong"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,1,31]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"Blender","year":"2025","unstructured":"2025. Blender. Retrieved from https:\/\/www.blender.org"},{"key":"e_1_3_3_3_2","volume-title":"Cyberpunk 2077","year":"2025","unstructured":"2025. Cyberpunk 2077. Retrieved from https:\/\/www.cyberpunk.net"},{"key":"e_1_3_3_4_2","volume-title":"Data Geocomm","year":"2025","unstructured":"2025. Data Geocomm. Retrieved from http:\/\/data.geocomm.com\/"},{"key":"e_1_3_3_5_2","volume-title":"Dijkstra\u2019s Shortest Path Algorithm Using Priority Queue","year":"2025","unstructured":"2025. Dijkstra\u2019s Shortest Path Algorithm Using Priority Queue. Retrieved from https:\/\/www.geeksforgeeks.org\/dsa\/dijkstras-shortest-path-algorithm-using-priority_queue-stl\/"},{"key":"e_1_3_3_6_2","volume-title":"Google Earth","year":"2025","unstructured":"2025. Google Earth. Retrieved from https:\/\/earth.google.com\/web"},{"key":"e_1_3_3_7_2","volume-title":"Google Map","year":"2025","unstructured":"2025. Google Map. Retrieved from https:\/\/www.google.com\/maps"},{"key":"e_1_3_3_8_2","volume-title":"Gunnison National Forest","year":"2025","unstructured":"2025. Gunnison National Forest. Retrieved from https:\/\/gunnisoncrestedbutte.com\/visit\/places-to-go\/parks-and-outdoors\/gunnison-national-forest\/"},{"key":"e_1_3_3_9_2","volume-title":"Laramie Mountain","year":"2025","unstructured":"2025. Laramie Mountain. Retrieved from https:\/\/www.britannica.com\/place\/Laramie-Mountains"},{"key":"e_1_3_3_10_2","volume-title":"Mars 2020 Mission Perseverance Rover Brains","year":"2025","unstructured":"2025. Mars 2020 Mission Perseverance Rover Brains. Retrieved from https:\/\/mars.nasa.gov\/mars2020\/spacecraft\/rover\/brains\/"},{"key":"e_1_3_3_11_2","volume-title":"NASA\u2019s Maven Observes Martian Light Show Caused by Major Solar Storm","year":"2025","unstructured":"2025. NASA\u2019s Maven Observes Martian Light Show Caused by Major Solar Storm. Retrieved from https:\/\/www.nasa.gov\/missions\/nasas-maven-observes-martian-light-show-caused-by-major-solar-storm\/"},{"key":"e_1_3_3_12_2","volume-title":"Preferred Walking Speed","year":"2025","unstructured":"2025. Preferred Walking Speed. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Preferred_walking_speed"},{"key":"e_1_3_3_13_2","volume-title":"Robinson Mountain","year":"2025","unstructured":"2025. Robinson Mountain. Retrieved from https:\/\/www.mountaineers.org\/activities\/routes-places\/robinson-mountain"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3678717.3691218"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3695830"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98601"},{"key":"e_1_3_3_18_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2022","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2022. Introduction to Algorithms. MIT Press."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.152"},{"key":"e_1_3_3_21_2","first-page":"151","volume-title":"International Workshop on Web and Wireless Geographical Information Systems (WWGIS)","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 Workshop on Web and Wireless Geographical Information Systems (WWGIS). 151\u2013166."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0053-2"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2016.02.002"},{"key":"e_1_3_3_25_2","volume-title":"Winter Hiking 101: Everything You Need to Know about Hiking in Snow","author":"Grid Fresh Off The","year":"2025","unstructured":"Fresh Off The Grid. 2025. Winter Hiking 101: Everything You Need to Know about Hiking in Snow. Retrieved from https:\/\/www.freshoffthegrid.com\/winter-hiking-101-hiking-in-snow\/"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588694"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850591"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732226"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0027-5"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989369"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_3_3_33_2","volume-title":"More Than 60 Killed in Blizzard Wreaking Havoc Across U.S.","author":"Aggarwal Mithil","year":"2022","unstructured":"Mithil Aggarwal. 2022. More Than 60 Killed in Blizzard Wreaking Havoc Across U.S. Retrieved from https:\/\/www.cnbc.com\/2022\/12\/26\/death-toll-rises-to-at-least-55-as-freezing-temperatures-and-heavy-snow-wallop-swaths-of-us.html"},{"key":"e_1_3_3_34_2","volume-title":"Mount Rainier","author":"Service National Park","year":"2022","unstructured":"National Park Service. 2022. Mount Rainier. Retrieved from https:\/\/www.nps.gov\/mora\/index.htm"},{"key":"e_1_3_3_35_2","volume-title":"Mount Rainier Annual Snowfall Totals","author":"Service National Park","year":"2025","unstructured":"National Park Service. 2025. Mount Rainier Annual Snowfall Totals. Retrieved from https:\/\/www.nps.gov\/mora\/planyourvisit\/annual-snowfall-totals.htm"},{"key":"e_1_3_3_36_2","volume-title":"Mount Rainier Frequently Asked Questions","author":"Service National Park","year":"2025","unstructured":"National Park Service. 2025. Mount Rainier Frequently Asked Questions. Retrieved from https:\/\/www.nps.gov\/mora\/faqs.htm"},{"key":"e_1_3_3_37_2","volume-title":"Measuring Snow","author":"Service National Weather","year":"2025","unstructured":"National Weather Service. 2025. Measuring Snow. Retrieved from https:\/\/www.weather.gov\/dvn\/snowmeasure"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.5555\/1018432.1021532"},{"key":"e_1_3_3_39_2","volume-title":"Exploring the Red Planet is a Costly Undertaking","author":"McCarthy Niall","year":"2021","unstructured":"Niall McCarthy. 2021. Exploring the Red Planet is a Costly Undertaking. Retrieved from https:\/\/www.statista.com\/chart\/24232\/life-cycle-costs-of-mars-missions\/"},{"issue":"15","key":"e_1_3_3_40_2","first-page":"212","article-title":"3D navigation mesh generation for path planning in uneven terrain","volume":"49","author":"P\u00fctz Sebastian","year":"2016","unstructured":"Sebastian P\u00fctz, Thomas Wiemann, Jochen Sprickerhof, and Joachim Hertzberg. 2016. 3D navigation mesh generation for path planning in uneven terrain. Symposium on Intelligent Autonomous Vehicles (IAV) 49, 15 (2016), 212\u2013217.","journal-title":"Symposium on Intelligent Autonomous Vehicles (IAV)"},{"key":"e_1_3_3_41_2","volume-title":"What Would Happen to me if I Was Buried Under Snow?","author":"LaDuca Russell","year":"2020","unstructured":"Russell LaDuca. 2020. What Would Happen to me if I Was Buried Under Snow? Retrieved from https:\/\/qr.ae\/prt6zQ"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453966"},{"key":"e_1_3_3_43_2","unstructured":"Barak Sober Robert Ravier and Ingrid Daubechies. 2020. Approximating the riemannian metric from point clouds via manifold moving least squares. arXiv:2007.09885. Retrieved from https:\/\/arxiv.org\/abs\/\/2007.09885"},{"key":"e_1_3_3_44_2","volume-title":"LiDAR Scanning with Spatial\u2019s Ios App","year":"2022","unstructured":"Spatial. 2022. LiDAR Scanning with Spatial\u2019s Ios App. Retrieved from https:\/\/support.spatial.io\/hc\/en-us\/articles\/360057387631-LiDAR-Scanning-with-Spatial-s-iOS-App"},{"key":"e_1_3_3_45_2","volume-title":"How is Snowfall Measured? A Meteorologist Explains How Volunteers Tally up Winter Storms","author":"Conversation The","year":"2025","unstructured":"The Conversation. 2025. How is Snowfall Measured? A Meteorologist Explains How Volunteers Tally up Winter Storms. Retrieved from https:\/\/theconversation.com\/how-is-snowfall-measured-a-meteorologist-explains-how-volunteers-tally-up-winter-storms-175628"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064038"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3563773"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3363147"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687753"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396880"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476319"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/MDM61037.2024.00023"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3639261"},{"key":"e_1_3_3_55_2","unstructured":"Yinzhao Yan and Raymond Chi-Wing Wong. 2025. Efficient path oracles for proximity queries on point clouds (technical report). Retrieved from https:\/\/github.com\/yanyinzhao\/PointCloudOracleCode\/blob\/main\/TechnicalReport.pdf"},{"key":"e_1_3_3_56_2","first-page":"1","volume-title":"ACM International Conference on Management of Data (SIGMOD)","volume":"3","author":"Yan Yinzhao","year":"2026","unstructured":"Yinzhao Yan and Raymond Chi-Wing Wong. 2026. Efficient proximity queries on simplified height maps. In ACM International Conference on Management of Data (SIGMOD), Vol. 3. 1\u201326."},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3484434"},{"key":"e_1_3_3_58_2","article-title":"Geodesics on point clouds","author":"Yu Hongchuan","year":"2014","unstructured":"Hongchuan Yu, Jian J Zhang, and Zheng Jiao. 2014. Geodesics on point clouds. Mathematical Problems in Engineering (MPE) 2014, 1 (2014), 1\u201312.","journal-title":"Mathematical Problems in Engineering (MPE)"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732225"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3576841.3585924"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.53"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687763"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.56"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389718"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3770577","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T12:46:01Z","timestamp":1769863561000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3770577"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,31]]},"references-count":63,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3770577"],"URL":"https:\/\/doi.org\/10.1145\/3770577","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,31]]},"assertion":[{"value":"2024-07-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-31","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}