一种极小化覆盖的空间索引结构——MCSI-树  

Minimizing Coverage Spatial Index Structure——MCSI-Tree

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

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

出　　处：《计算机工程》2009年第18期13-14,18,共3页Computer Engineering

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

摘　　要：以缩小各层节点覆盖为目标,运用数据空间分割技术,结合二叉树和R-树思想,提出一种空间数据索引结构——MCSI-树。在该结构中,空间数据之间的拓扑关系得到记载,各层节点的覆盖明显减少,查询区域减小,使区域查询速度得到提高。给出MCSI-树的建立算法及算法的正确性、可终止性证明及时间复杂度,并给出节点插入算法。An index structure ——MCSI-tree for spatial data is proposed by combining the division for spatial data objects with bi-tree and R-tree in order to reduce the coverage of the nodes on each level of the tree. In the structure, the topological relations between spatial data objects are recorded and the coverage of the nodes on each level of the tree is as small as possible so that the range query can be done faster. The algorithm for constructing the MCSI-tree, the proof of the algorithm＇s correctness and termination, and its time complexity are presented. The algorithm for node insertion is given.

关 键 词：空间索引 MCSI-树 极小化覆盖 

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