Research On Hybrid Index Method Based On 3D Grid-R Tree

With the development of computer technology,the amount of 3D spatial data is exponentially increasing.It is very important to set up an efficient indexing mechanism for spatial data.At present,it is difficult to meet the different requirements of 3D spatial data query and retrieval by a single index structure.The development of hybrid index structure has become a hotspot in 3D spatial index research.In view of the fact that the distribution of data in some 3D scenes in real life is not uniform,a hybrid index structure based on 3D Grid-R tree is proposed in this paper.And a variety of spatial query algorithms are proposed based on the structure of the spatial query algorithm.The main contents are as follows:Firstly,a 3D Grid-R tree hybrid index structure is proposed for the specific scene problem,and its feasibility analysis is given.On the basis of the design of the outer structure and the inner structure of the 3D Grid-R tree,this paper presents the design and implementation of the hybrid index structure.Next,we introduce a algorithm for updating the tree structure of 3D Grid-R tree,including insert operations,delete operations with detailed algorithm implementation with specific examples.Secondly,this paper introduces all kinds of query operations in the traditional R-tree structure.In order to improve the performance of spatial query,the query operation and algorithm based on the 3D Grid-R tree hybrid index structure are presented.The algorithms and advantages of precise query,region query and k-nearest neighbor query based on this structure are introduced respectively.The algorithm implementation and detailed algorithm analysis of the corresponding query operation are given,and the efficiency of query based on 3D Grid-R tree hybrid index structure is illustrated.Finally,the experimental system is constructed for the hybrid index structure,and the design idea of the system is given.The functions and operation examples of each part of the system are introduced respectively.The performance of different index structures under the same data set size is compared and analyzed.The 3D Grid-R tree hybrid index structure and the traditional R-tree index structure are constructed separately from the data sets with different data sizes and different 3D scenes.The comparison between the region query and the k-nearest neighbor query is carried out.The experimental results show the good performance of the 3D Grid-R tree hybrid index structure in the query method.