A Spatial Index Structure of Minimizing Overlap: MOSI-Tree

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.