留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用地球立体剖分格网生成Subdivision R-树索引模型

翟卫欣 程承旗 童晓冲 陈波

翟卫欣, 程承旗, 童晓冲, 陈波. 利用地球立体剖分格网生成Subdivision R-树索引模型[J]. 武汉大学学报 ● 信息科学版, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104
引用本文: 翟卫欣, 程承旗, 童晓冲, 陈波. 利用地球立体剖分格网生成Subdivision R-树索引模型[J]. 武汉大学学报 ● 信息科学版, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104
ZHAI Weixin, CHENG Chengqi, TONG Xiaochong, CHEN Bo. Subdivision R-Tree Index Model of the Earth-based Three-dimensional Subdivision Grids[J]. Geomatics and Information Science of Wuhan University, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104
Citation: ZHAI Weixin, CHENG Chengqi, TONG Xiaochong, CHEN Bo. Subdivision R-Tree Index Model of the Earth-based Three-dimensional Subdivision Grids[J]. Geomatics and Information Science of Wuhan University, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104

利用地球立体剖分格网生成Subdivision R-树索引模型

doi: 10.13203/j.whugis20140104
基金项目: 高分辨率对地观测系统国家重大专项(30-Y30B13-9003-14/16,03-Y30B06-9001-13/15);广西自然科学基金(2012GXNSFAA053181,2013GXNSFBA019265,2013GXNSFBA019266)。
详细信息
    作者简介:

    翟卫欣,博士,主要研究方向为空间数据库索引。pkuzhaiweixin@gmail.com

    通讯作者: 程承旗,博士,教授,博士生导师,主要研究方向为空天信息剖分组织理论。ccq@pku.edu.cn
  • 中图分类号: P208

Subdivision R-Tree Index Model of the Earth-based Three-dimensional Subdivision Grids

Funds: High Resolution Earth Observation System of National Major Special Project Funding, No.30-Y30B13-9003-14/16, 03-Y30B06-9001-13/15; Guangxi Natural Science Foundation of China, Nos.2012GXNSFAA053181, 2013GXNSFBA019265, 2013GXNSFBA019266.
  • 摘要: 针对三维数据管理中八叉树索引冗余多、R-树索引插入删除过程复杂的问题,依托GeoSOT地球立体剖分格网,提出了一种新的八叉树与R-树有机结合的Subdivision R-树索引模型(Subdivision R-tree)。首先,以GeoSOT地球立体剖分格网八叉树索引为基础构建了Subdivision R-树索引模型结构;随后,设计了Subdivision R-树索引模型基本的插入、删除、查询、分析算法;最后,开展了Subdivision R-树索引与原有数据索引性能对比试验,并对Subdivision R-树的阈值选取进行了相应分析。实验结果证明,Subdivision R-树的性能尤其是数据更新(插入、删除)等性能强于QR-树,随着数据分布的改变,性能提升更为明显,在数据分布较为集中的情况下,性能提升可达到20%。
  • [1] Chen Shupeng. Geo-spatial/temporal Analysis[J].Journal of Remote Sensing, 1997,1(3):161(陈述彭. 遥感地学分析的时空维[J]. 遥感学报,1997,1(3):161)
    [2] 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)
    [3] Finkel R A, Bentley J L. Quad Trees a Data Structure for Retrieval on Composite Keys[J]. Acta Informatica,1974,4(1):1-9
    [4] Guttman A.R-trees:A Dynamic Index Structure for Spatial Searching[J]. ACM, 1984,14(2):47-57
    [5] 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
    [6] Beckmann N, Kriegel H P, Schneider R, et al. The R*-tree:an Efficient and Robust Access Method for Points and Rectangles[J]. ACM, 1990,19(2):322-331
    [7] Kamel I, Faloutsos C. Hilbert R-tree:An Improved R-tree Using Fractals[OL]. http://drum.lib.umd.edu/handle/1903/5366,1993
    [8] 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
    [9] 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)
    [10] 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
    [11] Qiu Jianhua, Tang Guobing, Huang Huaguo. An Index Structure Based Quad-tree and R*-tree-QR*-tree[J]. Computer Applications, 2003, 23(8):124-126(邱建华, 唐学兵, 黄华国. 一种基于四叉树和R*-树的索引结构——QR*-树[J]. 计算机应用, 2003, 23(8):124-126)
    [12] 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)
    [13] 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)
    [14] 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)
    [15] 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)
    [16] 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)
    [17] Cheng Chengqi, Ren Fuhu, Pu Guolian, et al. Introduction to Spatial Information Subdivision Organization[M].Beijing:Science Press, 2012(程承旗,任伏虎,濮国梁,等. 空间信息剖分组织导论[M]. 北京:科学出版社,2012)
    [18] 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)
    [19] 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)
    [20] 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)
  • [1] 向隆刚, 高萌, 王德浩, 龚健雅.  Geohash-Trees:一种用于组织大规模轨迹的自适应索引 . 武汉大学学报 ● 信息科学版, 2019, 44(3): 436-442. doi: 10.13203/j.whugis20160523
    [2] 闫利, 胡晓斌, 谢洪.  车载LiDAR海量点云数据管理与可视化研究 . 武汉大学学报 ● 信息科学版, 2017, 42(8): 1131-1136. doi: 10.13203/j.whugis20150386
    [3] 李宇光, 李清泉.  利用地图栅格化的海量浮动车数据道路匹配快速算法 . 武汉大学学报 ● 信息科学版, 2014, 39(6): 724-728. doi: 10.13203/j.whugis20140071
    [4] 戴 晶, 吴明光, 郑培蓓, 王 蕾, 崔登吉, 陈泰生.  基于 hilbert曲线的str索引改进算法 . 武汉大学学报 ● 信息科学版, 2014, 39(7): 777-781.
    [5] 付仲良, 刘思远, 俞志强.  一种双映射变换的空间索引及空间连接算法研究 . 武汉大学学报 ● 信息科学版, 2014, 39(10): 1248-1251.
    [6] 邵华, 江南, 胡斌, 吕恒, 朱进.  利用GPU的R树细粒度并行STR方法批量构建 . 武汉大学学报 ● 信息科学版, 2014, 39(9): 1068-1073. doi: 10.13203/j.whugis20130158
    [7] 球体大圆弧QTM八叉树剖分 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 344-.
    [8] 蒋秉川, 游雄, 夏青, 田江鹏.  体素在虚拟地理环境构建中的应用技术研究 . 武汉大学学报 ● 信息科学版, 2013, 38(7): 875-878.
    [9] 王金鑫, 禄丰年, 郭同德, 陈 杰.  球体大圆弧QTM八叉树剖分 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 344-348.
    [10] 姜少波, 杨必胜, 孙轩.  特征保持的三维复杂建筑物模型多分辨率表达 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 902-905.
    [11] 陈静, 向隆刚, 朱欣焰.  分布式异构栅格数据的集成管理研究 . 武汉大学学报 ● 信息科学版, 2011, 36(9): 1094-1096.
    [12] 孙卡, 吴冲龙, 刘刚, 何珍文.  海量三维地质空间数据的自适应预调度方法 . 武汉大学学报 ● 信息科学版, 2011, 36(2): 140-143.
    [13] 龚俊, 谢潇.  基于R树索引的三维可视化查询方法 . 武汉大学学报 ● 信息科学版, 2011, 36(10): 1140-1143.
    [14] 程昌秀.  矢量数据多尺度空间索引方法的研究 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 597-601.
    [15] 周芹, 钟耳顺, 黄耀欢, 郭会.  大型空间数据库的并发索引策略CQR树 . 武汉大学学报 ● 信息科学版, 2009, 34(7): 856-858.
    [16] 陈鹏, 孟令奎, 宋杨.  三维GIS中基于空间拓扑约束条件的R树研究 . 武汉大学学报 ● 信息科学版, 2007, 32(4): 347-349.
    [17] 余亮, 边馥苓.  一种原生XML空间索引及查询语言 . 武汉大学学报 ● 信息科学版, 2006, 31(10): 936-939.
    [18] 郭晶, 刘广军, 董绪荣, 郭磊.  基于空间网格和Hilbert R-tree的二级R-tree空间索引 . 武汉大学学报 ● 信息科学版, 2005, 30(12): 1084-1088.
    [19] 郭菁, 郭薇, 胡志勇.  大型GIS空间数据库的有效索引结构QR-树 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 306-310.
    [20] 李清泉, 李德仁.  八叉树的三维行程编码 . 武汉大学学报 ● 信息科学版, 1997, 22(2): 102-106.
  • 加载中
计量
  • 文章访问数:  1353
  • HTML全文浏览量:  37
  • PDF下载量:  346
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-11-28
  • 刊出日期:  2016-04-05

利用地球立体剖分格网生成Subdivision R-树索引模型

doi: 10.13203/j.whugis20140104
    基金项目:  高分辨率对地观测系统国家重大专项(30-Y30B13-9003-14/16,03-Y30B06-9001-13/15);广西自然科学基金(2012GXNSFAA053181,2013GXNSFBA019265,2013GXNSFBA019266)。
    作者简介:

    翟卫欣,博士,主要研究方向为空间数据库索引。pkuzhaiweixin@gmail.com

    通讯作者: 程承旗,博士,教授,博士生导师,主要研究方向为空天信息剖分组织理论。ccq@pku.edu.cn
  • 中图分类号: P208

摘要: 针对三维数据管理中八叉树索引冗余多、R-树索引插入删除过程复杂的问题,依托GeoSOT地球立体剖分格网,提出了一种新的八叉树与R-树有机结合的Subdivision R-树索引模型(Subdivision R-tree)。首先,以GeoSOT地球立体剖分格网八叉树索引为基础构建了Subdivision R-树索引模型结构;随后,设计了Subdivision R-树索引模型基本的插入、删除、查询、分析算法;最后,开展了Subdivision R-树索引与原有数据索引性能对比试验,并对Subdivision R-树的阈值选取进行了相应分析。实验结果证明,Subdivision R-树的性能尤其是数据更新(插入、删除)等性能强于QR-树,随着数据分布的改变,性能提升更为明显,在数据分布较为集中的情况下,性能提升可达到20%。

English Abstract

翟卫欣, 程承旗, 童晓冲, 陈波. 利用地球立体剖分格网生成Subdivision R-树索引模型[J]. 武汉大学学报 ● 信息科学版, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104
引用本文: 翟卫欣, 程承旗, 童晓冲, 陈波. 利用地球立体剖分格网生成Subdivision R-树索引模型[J]. 武汉大学学报 ● 信息科学版, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104
ZHAI Weixin, CHENG Chengqi, TONG Xiaochong, CHEN Bo. Subdivision R-Tree Index Model of the Earth-based Three-dimensional Subdivision Grids[J]. Geomatics and Information Science of Wuhan University, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104
Citation: ZHAI Weixin, CHENG Chengqi, TONG Xiaochong, CHEN Bo. Subdivision R-Tree Index Model of the Earth-based Three-dimensional Subdivision Grids[J]. Geomatics and Information Science of Wuhan University, 2016, 41(4): 443-449. doi: 10.13203/j.whugis20140104
参考文献 (20)

目录

    /

    返回文章
    返回