基于三维网格-R树的混合索引方法研究  

Research on hybrid index method based on 3D grid-R tree

作　　者：刘永山[1] 龚翔 孔德瀚 单磊敬 LIU Yongshan;GONG Xiang;KONG Dehan;SHAN Leijing(School of Information Science and Engineering,Yanshan University,Qinhuangdao,Hebei 066004,China;Department of Information Science and Engineering,Hebei University of Environmental Engineering,Qinhuangdao,Hebei 066004,China;Rehabilitation Center of the Joint Logistic Support Force of the Chinese People's Liberation Army in Beidaihe,Qinhuangdao,Hebei 066100,China)

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]河北环境工程学院信息工程系,河北秦皇岛066102 [3]中国人民解放军联勤保障部队北戴河康复疗养中心,河北秦皇岛066100

出　　处：《燕山大学学报》2020年第2期138-149,共12页Journal of Yanshan University

基　　金：国家自然科学基金资助项目(61972334);河北省自然科学基金资助项目(F2017203019);河北省教育厅青年基金资助项目(QN2019044)。

摘　　要：针对三维场景下空间数据分布不均匀呈现区域密集的问题,本文提出并建立了三维网格-R树混合索引结构,在此基础上给出详细的维护与查询算法。该混合索引结构综合了网格快速划分三维空间以及R树高效查询的优点,较好地解决了海量非均匀分布的三维数据的快速管理、查询问题。最后针对上述混合索引结构模型构建了实验系统,对不同大小、不同分布下的数据集进行范围查询、k近邻查询对比测试,实验结果均表明了该混合索引结构在查询方面的良好性能。In this paper, a 3 D grid-R tree hybrid index structure is proposed and a detailed maintenance and query algorithm is proposed on the basis of the problem that the spatial distribution of spatial data is not uniform in the three-dimensional scene. This hybrid index structure comprehensive advantages of rapid three-dimensional space division of grids and the efficient query of R-tree, solves the problem of fast query of a large number of 3 D point metadata. Finally, according to the above hybrid index structure, the experiment system is constructed, and the data set of different sizes and different distribution is tested, and the experimental results show that the structure has good performance in terms of range query and k-nearest query.

关 键 词：空间数据 混合索引结构 网格 R树 三维网格-R树 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]