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.