摘要： 以缩小各层节点覆盖为目标，运用数据空间分割技术，结合二叉树和R-树思想，提出一种空间数据索引结构——MCSI-树。在该结构中，空间数据之间的拓扑关系得到记载，各层节点的覆盖明显减少，查询区域减小，使区域查询速度得到提高。给出MCSI -树的建立算法及算法的正确性、可终止性证明及时间复杂度，并给出节点插入算法。
关键词:
空间索引,
MCSI-树,
极小化覆盖
Abstract: 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.
Key words:
spatial index,
MCSI-tree,
minimizing coverage
中图分类号:
刘润涛;郝忠孝. 一种极小化覆盖的空间索引结构——MCSI-树[J]. 计算机工程, 2009, 35(18): 13-14.
LIU Run-tao; HAO Zhong-xiao. Minimizing Coverage Spatial Index Structure——MCSI-Tree[J]. Computer Engineering, 2009, 35(18): 13-14.