Multiscale Integer Coding and Data Index of 3D Spatial Grid

doi:10.11947/j.AGCS.2018.20170364

Abstract

Abstract: This paper proposed a multiscale integer coding and index method available for 3D spatial grid area based on the exiting problems of 3D spatial grid.This method used integer to unify coding the region divided by regular grid, formed a tree structure showed the size relationship and scale variation of grid which embodied the spatial relationships in different scale grid:include, be included, adjacent and so on, and achieved the unified integer coding of multi-scale grid in the end.On this basis, a serious of basic operation methods were also studied like:level operation, coordinate transformation operation between coding and grid, parent-unit query and sub-unit query.The contrast experiment was designed to compare this method with 3D R-tree index of Oracle Spatial.The result showed that, multiscale integer coding of 3D spatial grid was superior to the 3D R-tree of Oracle Spatial in data importing, index establishing and region querying, and the efficiency were enhanced about two times, forty-six times and four times respectively.

Key words: regular grid division, 3D spatial index, multiscale integer coding, coding operation, region query

CLC Number:

P237

LAI Guangling, TONG Xiaochong, DING Lu, QIN Zhiyuan. Multiscale Integer Coding and Data Index of 3D Spatial Grid[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(7): 1007-1017.

References

[1] BENTLEY J L. Multidimensional Binary Search Trees Used for Associative Searching[J]. Communications of the ACM, 1975, 18(9):509-517.
[2] GAEDE V, GVNTHER O. Multidimensional Access Methods[J]. ACM Computing Surveys, 1998, 30(2):170-231.
[3] 邵正伟, 席平. 基于八叉树编码的点云数据精简方法[J]. 工程图学学报, 2010, 31(4):73-76. SHAO Zhengwei, XI Ping. Data Reduction for Point Cloud Using Octree Coding[J]. Journal of Engineering Graphics, 2010, 31(4):73-76.
[4] 张会霞. 基于八叉树的点云数据的组织与可视化[J]. 太原师范学院学报(自然科学版), 2011, 10(3):128-132. ZHANG Huixia. The Organization and Visualization of Point Cloud Data Based on the Octree[J]. Journal of Taiyuan Normal University (Natural Science Edition), 2011, 10(3):128-132.
[5] 张传明, 潘懋, 徐绘宏. 基于分块混合八叉树编码的海量体视化研究[J]. 计算机工程, 2007, 33(14):33-35, 78. ZHANG Chuanming, PAN Mao, XU Huihong. Hybrid Blocking Octree-based Mass Volume Rendering[J]. Computer Engineering, 2007, 33(14):33-35, 78.
[6] 綦科, 谢冬青, 刘洁. 基于八叉树空间分割的三维点云模型密写[J]. 计算机工程, 2011, 37(4):7-9. QI Ke, XIE Dongqing, LIU Jie. 3D Point Cloud Model Steganography Based on Octree Space Division[J]. Computer Engineering, 2011, 37(4):7-9.
[7] 宋扬, 潘懋, 朱雷. 三维GIS中的R树索引研究[J]. 计算机工程与应用, 2004(14):9-10, 21. SONG Yang, PAN Mao, ZHU Lei. Study of R-tree Spatial Access Method in Three Dimensional GIS[J]. Computer Engineering and Applications, 2004(14):9-10, 21.
[8] BRAKATSOULAS S, PFOSER D, THEODORIDIS Y. Revisiting R-tree Construction Principles[C]//Proceedings of the 6th East European Conference on Advances in Databases and Information Systems. Bratislava, Slovakia:Springer, 2002:149-162.
[9] 郑坤, 朱良峰, 吴信才, 等. 3D GIS空间索引技术研究[J]. 地理与地理信息科学, 2006, 22(4):35-39. ZHENG Kun, ZHU Liangfeng, WU Xincai, et al. Study on Spatial Indexing Techniques for 3D GIS[J]. Geography and Geo-Information Science, 2006, 22(4):35-39.
[10] GUTTMAN A. R-trees:A Dynamic Index Structure for Spatial Searching[J]. ACM SIGMOD Record, 1984, 14(2):47-57.
[11] BECKMANN N, KRIEGEL H P, SCHNEIDER R, et al. The R-tree:An Efficient And Robust Access Method for Points and Rectangles[J]. ACM SIGMOD Record, 1990, 19(2):322-331.
[12] SELLIS T K, ROUSSOPOULOS N, FALOUTSOS C. The R+-tree:A Dynamic Index for Multi-dimensional Objects[C]//Proceedings of the 13th International Conference on Very Large Data Bases. San Francisco:Morgan Kaufmann Publishers, 1987:507-518.
[13] 邓红艳, 武芳, 翟仁健, 等. 一种用于空间数据多尺度表达的R树索引结构[J]. 计算机学报, 2009, 32(1):177-184. DENG Hongyan, WU Fang, ZHAI Renjian, et al. R-tree Index Structure for Multi-scale Representation of Spatial Data[J]. Chinese Journal of Computers, 2009, 32(1):177-184.
[14] 龚俊, 朱庆, 张叶廷, 等. 顾及多细节层次的三维R树索引扩展方法[J]. 测绘学报, 2011, 40(2):249-255. GONG Jun, ZHU Qing, ZHANG Yeting, et al. An Efficient 3D R-tree Extension Method Concerned With Levels of Detail[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(2):249-255.
[15] ROBINSON J T. The K-D-B-tree:A Search Structure for Large Multidimensional Dynamic Indexes[C]//Proceedings of the 1981 ACM SIGMOD international conference on Management of data. New York:ACM, 1981:10-18.
[16] 张泽宝. 空间数据库的索引技术研究[D]. 哈尔滨:哈尔滨工程大学, 2009. ZHANG Zebao. Research on Spatial Index Technology for Spatial Database[D]. Harbin:Harbin Engineering University, 2009.
[17] 张芩, 王振民. QR-树:一种基于R-树与四叉树的空间索引结构[J]. 计算机工程与应用, 2004(9):100-103. ZHANG Qin, WANG Zhenmin. QR-tree:A Kind of Spatial Index Structure Based on R-tree and Quad-tree[J]. Computer Engineering and Applications, 2004(9):100-103.
[18] 童晓冲, 贲进. 空间信息剖分组织的全球离散格网理论与方法[M]. 北京:测绘出版社, 2016. TONG Xiaochong, BEN Jin. The Principle and Method of Discrete Global Grid Systems for Geospatial Information Subdivision Organization Principle and Method of Discrete Global Grid Systems for Geospatial Information Subdivision Organization[M]. Beijing:Surveying and Mapping Press, 2016.
[19] 王晏民. 多比例尺GIS矢量空间数据组织研究[D]. 武汉:武汉大学, 2002. WANG Yanmin. Multiscale GIS Vector Spatial Data Organization Study[D]. Wuhan:Wuhan University, 2013.
[20] 夏宇, 朱欣焰, 李德仁. 空间信息多级网格索引技术研究[J]. 地理空间信息, 2006, 4(6):4-7. XIA Yu, ZHU Xinyan, LI Deren. Indexing Technology in Spatial Information Multi-grid[J]. Geospatial Information, 2006, 4(6):4-7.
[21] SAGAN H. Space-filling Curves[M]. New York:Springer-Verlag, 1994.
[22] 史绍雨, 唐新明, 吴凡, 等. 多级格网时空索引[J]. 测绘科学, 2006, 31(3):54-55. SHI Shaoyu, TANG Xinming, WU Fan, et al. Multi-level Grid Spatio-temporal Index[J]. Science of Surveying and Mapping, 2006, 31(3):54-55.
[23] 张小虎, 钟耳顺, 王少华, 等. 多尺度空间格网数据的索引编码研究[J]. 测绘通报, 2014(7):35-38. ZHANG Xiaohu, ZHONG Ershun, WANG Shaohua, et al. Research on Index and Code For Multi-scale Grid Data[J]. Bulletin of Surveying and Mapping, 2014(7):35-38.
[24] 周勇, 何建农, 凃平. 一种改进的自适应层次网格空间索引查询算法[J]. 计算机工程与应用, 2006, 42(7):159-161, 165. ZHOU Yong, HE Jiannong, TU Ping. An Algorithm of Improved Auto-selection Multi-layer Grid Spatial Index[J]. Computer Engineering and Applications, 2006, 42(7):159-161, 165.
[25] 童晓冲, 王嵘, 王林, 等. 一种有效的多尺度时间段剖分方法与整数编码计算[J]. 测绘学报, 2016, 45(S1):66-76. DOI:10.11947/j.AGCS.2016.F008. TONG Xiaochong, WANG Rong, WANG Lin, et al. An Efficient Integer Coding and Computing Method for Multiscale Time Segment[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):66-76. DOI:10.11947/j.AGCS.2016.F008.
[26] ORENSTEIN J A, MERRETT T H. A Class of Data Structures for Associative Searching[C]//Proceedings of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. Waterloo, Ontario, Canada:ACM, 1984:181-190.
[27] DAI H K, SU H C. Locality and Clustering Performances of Space-filling Curves[M]. Stillwater, OK, USA:Oklahoma State University, 2003:78-85.
[28] MURRAY C. Spatial and Graph Developer's Guide[DB/OL]. https://docs.oracle.com/database/121/SPATL/, 2017-01/2017-11.
[29] MURRAY C. Oracle Spatial User's Guide and Reference, Release 9.2[DB/OL], https://docs.oracle.com/cd/B10501_01/appdev.920/a96630.pdf, 2002-03/2017-11.
[30] RAVADA S, KAZAR B M, KOTHURI R. Query Processing in 3D Spatial Databases:Experiences with Oracle Spatial 11g[M]//LEE J, ZLATANOVA S. 3D Geo-information Sciences. Berlin:Springer, 2009:153-173.
[31] STOTER J E, ZLATANOVA S. 3D GIS, Where are We Standing?[C]//ISPRS Joint Workshop on ‘Spatial, Temporal and Multi-dimensional Data Modelling and Analysis’. Québec:ISPRS, 2003.
[32] BRAKATSOULAS S, PFOSER D, TRYFONA N. Modeling, Storing and Mining Moving Object Databases[C]//Proceedings of 2004 International Database Engineering and Applications Symposium. Coimbra:IEEE, 2004:68-77.