R-树和四叉树的空间索引结构:RQOP_树  

Spatial index structure based on R-tree and quadtree:RQOP_tree

作　　者：刘润涛[1] 郝忠孝[1,2] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《哈尔滨工业大学学报》2010年第2期323-327,共5页Journal of Harbin Institute of Technology

基　　金：国家自然科学基金资助项目(10571037);黑龙江省自然科学基金资助项目(F200601)

摘　　要：针对现有的基于R-树和四叉树的空间索引结构中存在的问题,通过建立数据矩形间的序关系对数据空间进行分割,提出了一种新的空间数据索引结构:RQOP树.在此结构中,节点的构造是按照空间数据的分布来进行的而不是像其它基于R-树和四叉树的空间索引结构只是对数据空间进行均匀划分而得到,使树的高度尽可能低,同时使兄弟节点间的交叠相对较小.在区域查询算法中引入了查询窗口包含节点MBR的判断加快了查询的速度.给出了RQOP树的生成、节点插入和区域查询算法,并给出了相应算法的可行性和正确性定理及时间复杂度分析.实验表明:新索引结构的查询速度明显加快.A new index structure for spatial data, RQOP_ tree, is proposed by setting up the order relation between data rectangles to partition the data spaces, aimed at the existing problems in current index structures based on R-tree and quadtree. In this structure, the middle nodes are constructed according to the distribution of spatial data instead of partitioning the data space evenly, therefore the height of the tree is guaranteed as low as possible and a comparatively small overlap between brother nodes can be kept. In the range query algo-rithm, the check of query window containing a node＇ s MBR is introduced to speed up the query effectively for a comparatively large query window. The algorithm for constructing the index structure is given, and its time complexity as well as its correctness is presented. The algorithms for node insertion and range query are obtained. The experiment shows that the query speed is increased greatly.

关 键 词：空间数据 索引结构 RQOP树 区域查询 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]