一种极小化交叠的空间索引结构——MOSI-树

A Spatial Index Structure of Minimizing Overlap: MOSI-Tree

以缩小同层节点间交叠为目标,提出了一种空间数据索引结构——MOSI-树.通过定义数据间的序关系对数据空间分割,尽可能使空间位置相邻的数据分配在同一节点中,从而使MOSI-树的同层节点间的交叠有效减少.给出了MOSI-树的建立算法及算法的正确性、可终止性证明及时间复杂度,并给出了节点插入算法.实验结果表明,MOSI-树上同层节点间交叠明显减少.

An index structure： MOSI-tree for spatial data,is proposed for the purpose of reducing the overlap among the nodes on the same level of the tree. The data,whose spatial positions are adjacent,are allocated into the same node as far as possible by partitioning the data space in orders between the data defined in this paper to make the overlap among the nodes on the same level of the tree reduce effectively. An algorithm for constructing the MOSI-tree is proposed,and the algorithm is proved to be correct. And the termination and the time complexity of the algorithm are also presented. Finally,the algorithm for node insertion is obtained. Experiment shows that the overlap among the nodes on the same level of MOSI-tree is reduced evidently.