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

ZHAI Weixin; CHENG Chengqi; TONG Xiaochong; CHEN Bo

doi:10.13203/j.whugis20140104

Volume 41 Issue 4

Apr. 2016

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 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:

PDF (429 KB)

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

1.
Institute of Remote Sensing and GIS, Peking University, Beijing 100871, China;
2.
College of Engineering, Peking University, Beijing 100871, China;
3.
State Key Laboratory of Earth Surface Process and Resource Ecology, Beijing Normal University, Beijing 100875, China;
4.
Air Force Airborne Academy, Guilin 541003, China

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.

More Information

Received Date: November 27, 2014
Published Date: April 04, 2016

Graphical Abstract

Abstract

Abstract

There are redundant complex issues concerning insertion and deletion processes in three-dimensional octree and R-tree index data management. Relying on GeoSOT Earth three-dimensional subdivision grids, we propose a new complex combination of the octree and R-tree indexes, the Subdivision R-tree model(Subdivision R-tree). First, GeoSOT three-dimensional subdivision octree-based grid index is used to construct a model Subdivision R-tree index structure. Subsequently, the basic design of the insertion, deletion, and query algorithm Subdivision R-tree index, is analyzed. Finally, we carry out a Subdivision R-tree indexing operation with the original data indexing performance comparison test, and discuss the threshold selection of Subdivision R-tree analysis accordingly. Test results show that the performance, especially Subdivision R-tree data update(insertionor deletion) process is better than octree. With the change of data distribution, the performance is more evident in the case that the data distribution is more concentrated, and the improvement is up to 20%.
- spatial index,
- Subdivision R-tree,
- subdivision,
- GeoSOT

FullText(HTML)

References (20)

References

[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]	NIU Quanfu, LIU Mingzhi, ZHANG Man, CHENG Weiming. Vegetation Dynamic Change and Its Response to Climate and Topography in Altay Region of Xinjiang in Recent 20 Years[J]. Geomatics and Information Science of Wuhan University, 2023, 48(9): 1522-1530. DOI: 10.13203/j.whugis20210189
[2]	ZHANG Chen, HE Biao, GUO Renzhong, MA Ding, CHEN Yebin. A Data Conversion Method from Oblique Photogrammetric 3D Models to Renderable Assets in Unreal Engine 4[J]. Geomatics and Information Science of Wuhan University, 2023, 48(4): 514-524. DOI: 10.13203/j.whugis20210574
[3]	WANG Pengxin, CHEN Chi, ZHANG Yue, ZHANG Shuyu, LIU Junming. Estimation of Winter Wheat Yield Using Assimilated Bi-variables and PCA-Copula Method[J]. Geomatics and Information Science of Wuhan University, 2022, 47(8): 1201-1212. DOI: 10.13203/j.whugis20220038
[4]	LEI Lei, LI Zhenhong, YANG Hao, YANG Guijun. Extraction of the Leaf Area Density of Maize Using UAV-LiDAR Data[J]. Geomatics and Information Science of Wuhan University, 2021, 46(11): 1737-1745. DOI: 10.13203/j.whugis20200674
[5]	YU Ying, SONG Zhangliang, FAN Wenyi, YANG Xiguang. Scale Conversion from Canopy Spectra to Leaf Spectra[J]. Geomatics and Information Science of Wuhan University, 2018, 43(10): 1560-1565, 1573. DOI: 10.13203/j.whugis20160552
[6]	QIN Zhanfei, SHEN Jian, XIE Baoni, YAN Lin, CHANG Qingrui. Hyperspectral Estimation Model for Predicting LAI of Rice in Ningxia Irrigation Zone[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1159-1166. DOI: 10.13203/j.whugis20150132
[7]	ZHANG Xun, ZHONG Ershun, ZHANG Xiaohu, WANG Shaohua, LI Shaojun. A Modified Algorithm to Construct Gridded Area Cartogramsby Scale Effect Index[J]. Geomatics and Information Science of Wuhan University, 2015, 40(8): 1100-1104. DOI: 10.13203/j.whugis20130370
[8]	LIU　Hui. Extraction　of 　the　Floor　Area　Ratio　in 　the　Central　District 　of 　Fuzhou　Cit y Based　on　an　Improved　Shadow　Index　Model[J]. Geomatics and Information Science of Wuhan University, 2014, 39(10): 1241-1247.
[9]	XIONG Jinguo, WANG Shixin, ZHOU Yi, Yan Fuli. Influence of Landscape Pattern Index on the Area Extracted from ETM~+ and MODIS[J]. Geomatics and Information Science of Wuhan University, 2011, 36(1): 98-103.
[10]	WANG Xiaohong, LIU Yaolin, DU Xiao. Drought Monitoring Using Vegetation Leaf Water in China[J]. Geomatics and Information Science of Wuhan University, 2007, 32(6): 498-501.

Cited By

Get Citation

PDF

XML

Article views (1710) PDF downloads (357)

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

Abstract

References

Related Articles

Catalog

Related

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

Abstract

References

Related Articles

Catalog

Related

Export File

Citation

Format

Content