基于多序的空间数据索引结构——MOIS-树  

A Multi-Order Based Index Structure for Spatial Data—MOIS-tree

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

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

出　　处：《计算机研究与发展》2010年第5期849-857,共9页Journal of Computer Research and Development

基　　金：黑龙江省自然科学基金项目(F200601);国家自然科学基金项目(10571037);黑龙江省教育厅科学技术研究基金项目(11511027)~~

摘　　要：以提高查询效率为目标,运用数据空间分割技术、结合B-树和R-树思想,提出了一种空间数据索引结构——MOIS-树,给出了全新的区域查询处理方法和空间对象按其MBR进行排序的4种序关系定义,并以此为基础给出了MOIS-树的定义,规定MOIS-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,从而使得在中间节点中进行查询时可以进行快速定位,明显地加快了查询的速度.此外,在查询算法中引入查询窗口包含中间节点MBR的检测,对于较大查询窗口的查询,有效地减少了常规查询算法中大量无效的相交性判断,从另一方面加快了查询速度.给出了MOIS-树的建立算法、节点插入算法及算法的正确性、可终止性证明及时间复杂度分析,并给出区域查询算法及算法的性能分析.实验表明,索引结构区域查询速度有很大的提高.An index structure,MOIS-tree for spatial data,is proposed by combining the division for data space with B-tree and R-tree at the aim of improving query efficiency,which is a brand new way to process range query.The definitions of the four kinds of orders,in which spatial data are ordered according to their MBRs,are given.Based on the orders,the definition of MOIS-tree is given.In the MOIS-tree the children nodes of each middle node are ordered according to their geometric locations so that the position can be located effectively to find queried results quickly when range query is processed in a middle node.Besides,the check of query window＇s containing a middle node in the range query algorithm of new index structure is introduced to reduce a great number of noneffective intersection tests in general query algorithms.Thus the query efficiency is achieved greatly in another aspect.The algorithms for constructing a MOIS-tree and node insertion,and the proofs of the algorithms＇ correctness and termination are presented and their time complexities are given.Finally,the algorithm for range query is obtained and the analysis for its properties is condacted.The experimental results show that the speed of range query on MOIS-tree is greatly improved.

关 键 词：空间数据库 索引结构 MOIS-树 多序 区域查询 

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