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

摘要： 以缩小各层节点覆盖为目标，运用数据空间分割技术，结合二叉树和R-树思想，提出一种空间数据索引结构——MCSI-树。在该结构中，空间数据之间的拓扑关系得到记载，各层节点的覆盖明显减少，查询区域减小，使区域查询速度得到提高。给出MCSI -树的建立算法及算法的正确性、可终止性证明及时间复杂度，并给出节点插入算法。

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

CLC Number: 

• TP311