|
|
- 2016
利用地球立体剖分格网生成Subdivision R-树索引模型
|
Abstract:
针对三维数据管理中八叉树索引冗余多、R-树索引插入删除过程复杂的问题,依托GeoSOT地球立体剖分格网,提出了一种新的八叉树与R-树有机结合的Subdivision R-树索引模型(Subdivision R-tree)。首先,以GeoSOT地球立体剖分格网八叉树索引为基础构建了Subdivision R-树索引模型结构;随后,设计了Subdivision R-树索引模型基本的插入、删除、查询、分析算法;最后,开展了Subdivision R-树索引与原有数据索引性能对比试验,并对Subdivision R-树的阈值选取进行了相应分析。实验结果证明,Subdivision R-树的性能尤其是数据更新(插入、删除)等性能强于QR-树,随着数据分布的改变,性能提升更为明显,在数据分布较为集中的情况下,性能提升可达到20%
| [1] | Finkel R A, Bentley J L. Quad Trees a Data Structure for Retrieval on Composite Keys[J]. Acta Informatica,1974,4(1):1-9 |
| [2] | Guttman A.R-trees:A Dynamic Index Structure for Spatial Searching[J]. ACM, 1984,14(2):47-57 |
| [3] | Beckmann N, Kriegel H P, Schneider R, et al. The R<sup>*</sup>-tree:an Efficient and Robust Access Method for Points and Rectangles[J]. ACM, 1990,19(2):322-331 |
| [4] | Kamel I, Faloutsos C. Hilbert R-tree:An Improved R-tree Using Fractals[OL]. http://drum.lib.umd.edu/handle/1903/5366,1993 |
| [5] | Fu Y C, Hu Z Y, Guo W, et al. QR-tree:a Hybrid Spatial Index Structure[C]. Machine Learning and Cybernetics, 2003 International Conference, Xi'an, China, 2003 |
| [6] | Tan Wenken, Wang Changhon,Shi Yishao. Digital Underground Spatial Indexing QR-tree Based on XML[J]. Journal of Zhejiang University(Engineering Science), 2009,9:1615-1620(谭文垦, 王长虹, 石忆邵. 基于XML的数字地下空间索引QR树研究[J]. 浙江大学学报:工学版, 2009,9:1615-1620) |
| [7] | Cheng Chengqi, Ren Fuhu, Pu Guolian, et al. Introduction to Spatial Information Subdivision Organization[M].Beijing:Science Press, 2012(程承旗,任伏虎,濮国梁,等. 空间信息剖分组织导论[M]. 北京:科学出版社,2012) |
| [8] | Qiu Jianhua, Tang Guobing, Huang Huaguo. An Index Structure Based Quad-tree and R<sup>*</sup>-tree-QR<sup>*</sup>-tree[J]. Computer Applications, 2003, 23(8):124-126(邱建华, 唐学兵, 黄华国. 一种基于四叉树和R<sup>*</sup>-树的索引结构——QR<sup>*</sup>-树[J]. 计算机应用, 2003, 23(8):124-126) |
| [9] | Li Deren, Zhu Xinyan, Gong Jianya. From Digital Map to Spatial Information Multi-grid-A Thought of Spatial Information Multi2grid Theory[J]. Geomatics and Information Science of Wuhan University, 2004, 28(6):642-650(李德仁, 朱欣焰, 龚健雅. 从数字地图到空间信息网格——空间信息多级网格理论思考[J]. 武汉大学学报·信息科学版, 2004, 28(6):642-650) |
| [10] | Song Shuhua, Cheng Chengqi, Guan Li, et al. Analysis on Global Geodata Partitioning Models[J]. Geography and Geo-information Science, 2008, 24(4):11-15(宋树华, 程承旗, 关丽, 等. 全球空间数据剖分模型分析[J]. 地理与地理信息科学, 2008, 24(4):11-15) |
| [11] | Jin An, Cheng Chengqi. Spatial Data Coding Method Based on Global Subdivision Grid[J]. Journal of Geomatics Science and Technology, 2013, 30(3):284-287(金安, 程承旗. 基于全球剖分网格的空间数据编码方法[J]. 测绘科学技术学报, 2013, 30(3):284-287) |
| [12] | Chen Shupeng. Geo-spatial/temporal Analysis[J].Journal of Remote Sensing, 1997,1(3):161(陈述彭. 遥感地学分析的时空维[J]. 遥感学报,1997,1(3):161) |
| [13] | Li Guojie, Cheng Xueqi. Research Status and Scientific Thinking of Big Data[J]. Bulletin of Chinese Academy of Sciences, 2012,27(6):647-657(李国杰,程学旗. 大数据研究:未来科技及经济社会发展的重大战略领域——大数据的研究现状与科学思考[J]. 中国科学院院刊,2012,27(6):647-657) |
| [14] | Sellis T, Roussopoulos N, Faloutsos C. The R+-tree:A Dynamic Index for Multi-dimensional Objects[OL].http://repository.cmu.edu/cgi/viewcontent.cgi?article=1563&context=compsci,2015 |
| [15] | Kothuri R K V, Ravada S, Abugov D. Quadtree and R-tree Indexes in Oracle Spatial:A Comparison Using GIS Data[C]. The 2002 ACM SIGMOD International Conference on Management of Data, Wisconsin, USA,2002 |
| [16] | Guo Jing, Guo Wei, Hu Zhiyong. QR-tree:An Efficient Spatial Indexing Structure for GIS with very Large Spatial Database[J]. Geomatics and Information Science of Wuhan University, 2003, 28(3):306-310(郭菁,郭薇,胡志勇. 大型空间数据库的有效索引结构QR-树[J]. 武汉大学学报·信息科学版,2003, 28(3):306-310) |
| [17] | Huang Ming, Chen Zhe. Research on the Spatial Index Based on Improvement QR Tree[J]. Journal of Heilongjiang Institute of Technology, 2005, 19(3):18-20(黄明, 陈哲. 基于改进QR-树的空间数据索引的研究[J]. 黑龙江工程学院学报, 2005, 19(3):18-20) |
| [18] | Zhao Nan, Hao Zhongxiao. A Hybrid Structure of Spatial Multilevel Index Based on Grids and R-Tree[J].Computer Technology and Development, 2009, 19(3):91-94(赵楠, 郝忠孝. 一种基于网格与R树的多级混合索引[J]. 计算机技术与发展, 2009, 19(3):91-94) |
| [19] | Zhao Lingli, Zhao Renliang, Zhu Jianjun,et al. A Data Integration Hiberarchy Index Tree Oriented to Urbanization System[J]. Geomatics and Information Science of Wuhan University, 2010, 35(12):1486-1490(赵伶俐, 赵仁亮, 朱建军, 等. 一种面向城镇化系统数据整合的层次索引树[J]. 武汉大学学报·信息科学版, 2010, 35(12):1486-1490) |
| [20] | Bi Yuekun, Liu Pengju, Li Chunqiu. R-tree-based Maritime Mobile Ad Hoc Networks Spatial Index[J]. China Water Transport, 2013,9:64-65(毕月琨, 刘鹏举, 李春秋. 基于R树的海上移动自组网空间索引[J]. 中国水运, 2013,9:64-65) |
