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

A Spatial Index Structure of Minimizing Overlap: MOSI-Tree

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

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

出　　处：《北京工业大学学报》2010年第10期1423-1427,1432,共6页Journal of Beijing University of Technology

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

摘　　要：以缩小同层节点间交叠为目标,提出了一种空间数据索引结构——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.

关 键 词：空间索引 MOSI-树 极小化交叠 区域查询 

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