Bo Huang
Raymond Chi-Wing Wong
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
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.
Supplemental Material
- 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.Google Scholar
- Lyudmil Aleksandrov, Hristo N Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, and Jörg-Rüdiger Sack. 2010. Algorithms for approximate shortest path queries on weighted polyhedral surfaces. In Discrete & Computational Geometry. 762--801.Google Scholar
- Lyudmil Aleksandrov, Hristo N Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, and Jörg-Rüdiger Sack. 2010. Algorithms for approximate shortest path queries on weighted polyhedral surfaces. In Discrete & Computational Geometry. 762--801.Google Scholar
- Lyudmil Aleksandrov, Anil Maheshwari, and J-R Sack. 2005. Determining approximate shortest paths on weighted polyhedral surfaces. Journal of ACM, 25--53.Google ScholarDigital Library
- Paul B Callahan and S Rao Kosaraju. 1995. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of ACM, 67--90.Google ScholarDigital Library
- Marcel Campen, Martin Heistermann, and Leif Kobbelt. 2013. Practical Anisotropic Geodesy. Comput. Graph. Forum, 63--71.Google Scholar
- Nathaniel Chaney, Laura Torres-Rojas, and Jason Simon. 2021. Leveraging clustering and geostatistics to improve the modeling of sub-grid land-atmosphere interactions in Earth system models. In EGU General Assembly Conference Abstracts. EGU21--14039.Google ScholarCross Ref
- Jindong Chen and Yijie Han. 1990. Shortest paths on a polyhedron. In International Symposium on Computational Geometry (SoCG). 360--369.Google ScholarDigital Library
- Paolo Cignoni, Marco Callieri, Massimiliano Corsini, Matteo Dellepiane, Fabio Ganovelli, and Guido Ranzuglia. 2008. MeshLab: an Open-Source Mesh Processing Tool. In Eurographics Italian Chapter Conference, Vittorio Scarano, Rosario De Chiara, and Ugo Erra (Eds.). The Eurographics Association. https: //doi.org/10.2312/LocalChapterEvents/ItalChap/ItalianChapConf2008/129--136Google Scholar
- 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).Google Scholar
- Ke Deng, Heng Tao Shen, Kai Xu, and Xuemin Lin. 2006. Surface k-NN query processing. In IEEE International Conference on Data Engineering (ICDE). 78.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Brett G Dickson and Paul Beier. 2007. Quantifying the influence of topographic position on cougar (Puma concolor) movement in southern California, USA. Journal of Zoology, 270--277.Google ScholarCross Ref
- Hristo N Djidjev and Christian Sommer. 2011. Approximate distance queries forweighted polyhedral surfaces. In The European Symposium on Algorithms (ESA). 579--590.Google Scholar
- Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Experimental Algorithms.Google Scholar
- Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks using contraction hierarchies. Transportation Science (2012).Google Scholar
- Wei Hu. 2008. Co-location Pattern Discovery. Springer US, 98--103.Google Scholar
- 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/technicalreportGoogle Scholar
- S. A. Huettel, A. W. Song, and G. McCarthy. 2004. Functional magnetic resonance imaging. In Sinauer Associates.Google Scholar
- 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 Proceedings Geometric Modeling and Processing 2000. Theory and Applications (GMPTA). 241--250.Google ScholarCross Ref
- Manohar Kaul, Raymond Chi-WingWong, and Christian S Jensen. 2015. New lower and upper bounds for shortest distance queries on terrains. ACM International Conference on Very Large Data Bases (VLDB), 168--179.Google ScholarDigital Library
- Manohar Kaul, Raymond Chi-Wing Wong, Bin Yang, and Christian S Jensen. 2013. Finding shortest paths on terrains by killing two birds with one stone. In ACM International Conference on Very Large Data Bases (VLDB). 73--84.Google ScholarDigital Library
- Stephen Kiazyk, Sébastien Loriot, and Éric Colin de Verdière. 2021. Triangulated Surface Mesh Shortest Paths. In CGAL User and Reference Manual. CGAL Editorial Board. https://doc.cgal.org/5.3/Manual/packages.html# PkgSurfaceMeshShortestPathGoogle Scholar
- 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.Google Scholar
- Mark Lanthier, Anil Maheshwari, and J-R Sack. 2001. Approximating shortest paths on weighted polyhedral surfaces. Algorithmica, 527--562.Google Scholar
- 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.13486Google Scholar
- 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).Google Scholar
- Lian Liu and Raymond Chi-WingWong. 2011. Finding shortest path on land surface. In ACM Conference on Management of Data (SIGMOD). 433--444.Google ScholarDigital Library
- Anders Mårell, John P Ball, and Annika Hofgaard. 2002. Foraging and movement paths of female reindeer: insights from fractal analysis, correlated random walks, and Lévy flights. Canadian Journal of Zoology, 854--865.Google Scholar
- Joseph SB Mitchell, David M Mount, and Christos H Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput., 647--668.Google Scholar
- 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.Google Scholar
- L Tiina Sarjakoski, Pyry Kettunen, Hanna-Marika Flink, Mari Laakso, Mikko Rönneberg, and Tapani Sarjakoski. 2012. Analysis of verbal route descriptions and landmarks for hiking. Personal and Ubiquitous Computing, 1001--1011.Google Scholar
- Cyrus Shahabi, Lu-An Tang, and Songhua Xing. 2008. Indexing land surface for efficient knn query. In ACM International Conference on Very Large Data Bases (VLDB). 1020--1031.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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/G98K778DGoogle Scholar
- The CGAL Project. 2021. CGAL User and Reference Manual. CGAL Editorial Board. https://doc.cgal.org/5.3/ Manual/packages.htmlGoogle Scholar
- Nguyet Tran, Michael J Dinneen, and Simone Linz. 2020. Close Weighted Shortest Paths on 3D Terrain Surfaces. In The ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2021 (SIGSPATIAL). 597--607.Google ScholarDigital Library
- 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öppen climate zones in the contiguous United States. Landscape and urban planning 192 (2019), 103668.Google Scholar
- Victor Junqiu Wei, Raymond Chi-Wing Wong, Cheng Long, David M. Mount, and Hanan Samet. 2022. Proximity Queries on Terrain Surface. ACM Trans. Database Syst. 47, 4 (2022), 15:1--15:59. https://doi.org/10. 1145/3563773Google ScholarDigital Library
- 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.Google Scholar
- Shi-Qing Xin and Guo-Jin Wang. 2009. Improving Chen and Han's Algorithm on the Discrete Geodesic Problem. ACM Transactions on Graphics (TOG), 104:1--104:8.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
Index Terms
- EAR-Oracle: On Efficient Indexing for Distance Queries between Arbitrary Points on Terrain Surface
Recommendations
Distance Oracle on Terrain Surface
SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of DataDue to the advance of the geo-spatial positioning and the computer graphics technology, digital terrain data become more and more popular nowadays. Query processing on terrain data has attracted considerable attention from both the academic community ...
Distance queries for complex spatial objects in oracle spatial
SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsWith the proliferation of global positioning systems (GPS) enabled devices, a growing number of database systems are capable of storing and querying different spatial objects including points, polylines and polygons. In this paper, we present our ...
Proximity Queries on Terrain Surface
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 ...
Comments