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

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

摘要:

针对现有的基于R-树和四叉树的空间索引结构中存在的问题,通过建立数据矩形间的序关系对数据空间进行分割,提出了一种新的空间数据索引结构:RQOP树.在此结构中,节点的构造是按照空间数据的分布来进行的而不是像其它基于R-树和四叉树的空间索引结构只是对数据空间进行均匀划分而得到,使树的高度尽可能低,同时使兄弟节点间的交叠相对较小.在区域查询算法中引入了查询窗口包含节点MBR的判断加快了查询的速度.给出了RQOP树的生成、节点插入和区域查询算法,并给出了相应算法的可行性和正确性定理及时间复杂度分析.实验表明:新索引结构的查询速度明显加快.

Abstract:

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 algorithm,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.