高级检索
    刘润涛, 郝忠孝. 基于多序的空间数据索引结构——MOIS-树[J]. 计算机研究与发展, 2010, 47(5): 849-857.
    引用本文: 刘润涛, 郝忠孝. 基于多序的空间数据索引结构——MOIS-树[J]. 计算机研究与发展, 2010, 47(5): 849-857.
    Liu Runtao, Hao Zhongxiao. A Multi-Order Based Index Structure for Spatial Data—MOIS-tree[J]. Journal of Computer Research and Development, 2010, 47(5): 849-857.
    Citation: Liu Runtao, Hao Zhongxiao. A Multi-Order Based Index Structure for Spatial Data—MOIS-tree[J]. Journal of Computer Research and Development, 2010, 47(5): 849-857.

    基于多序的空间数据索引结构——MOIS-树

    A Multi-Order Based Index Structure for Spatial Data—MOIS-tree

    • 摘要: 以提高查询效率为目标,运用数据空间分割技术、结合B-树和R-树思想,提出了一种空间数据索引结构——MOIS-树,给出了全新的区域查询处理方法和空间对象按其MBR进行排序的4种序关系定义,并以此为基础给出了MOIS-树的定义,规定MOIS-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,从而使得在中间节点中进行查询时可以进行快速定位,明显地加快了查询的速度.此外,在查询算法中引入查询窗口包含中间节点MBR的检测,对于较大查询窗口的查询,有效地减少了常规查询算法中大量无效的相交性判断,从另一方面加快了查询速度.给出了MOIS-树的建立算法、节点插入算法及算法的正确性、可终止性证明及时间复杂度分析,并给出区域查询算法及算法的性能分析.实验表明,索引结构区域查询速度有很大的提高.

       

      Abstract: An index structure, MOIS-tree for spatial data, is proposed by combining the division for data space with B-tree and R-tree at the aim of improving query efficiency, which is a brand new way to process range query. The definitions of the four kinds of orders, in which spatial data are ordered according to their MBRs, are given. Based on the orders, the definition of MOIS-tree is given. In the MOIS-tree the children nodes of each middle node are ordered according to their geometric locations so that the position can be located effectively to find queried results quickly when range query is processed in a middle node. Besides, the check of query window's containing a middle node in the range query algorithm of new index structure is introduced to reduce a great number of noneffective intersection tests in general query algorithms. Thus the query efficiency is achieved greatly in another aspect. The algorithms for constructing a MOIS-tree and node insertion, and the proofs of the algorithms' correctness and termination are presented and their time complexities are given. Finally, the algorithm for range query is obtained and the analysis for its properties is condacted. The experimental results show that the speed of range query on MOIS-tree is greatly improved.

       

    /

    返回文章
    返回