Advanced Search
    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.

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

    • 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.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return