Research On The Technology Of Multi-approximate Sptail Index And Spatial Data Search

With the unceasing spread and deepening of GIS applications, the wide range of spatial data also is increasing, which needs spatial database system that is the core of GIS has a fast search capabilities. The spatial data index is one of the key technologies in spatial database system, and the spatial index directly affects the performance of spatial databases, and the spatial index affects the search performance of spatial database. Therefore, many domestic and foreign scholars present a variety of spatial data index technologies, which are mainly concentrated in the perspective of optimizing algorithm to enhance search performance. But the space of enhancing search performance is very limited. To solve this problem, this paper study the constructing spatial index with multi-approximate graph of spatial object and the relative spatial data search with the strategy of increasing the space to reduce the time based on the research of former scholars for the spatial index and query. A new research idea and method is provided to enhance the search capabilities of spatial data by a greater extent. The research work is relied on the project of the study of multi-approximate method for massive spatial data, and a theoretical research results are made based on the above the questions and research ideas, which is that the index method can obtain better searching efficiency of spatial data. So a new method of spatial index is provided, which can be more efficient on window scope, nearest distance and semi-join query in the massive spatial data and in GIS system.Firstly, these are discussed in the paper about the characteristics of spatial data, the keys of technology for spatial database and spatial relations containing topological relations, distance relations and direction relations. And the external and interior approximate expressiones of spatial object are analysised. Then the spatial index is constructed which includes not only the external approximate expression but also interior approximate expression of spatial object and is extended from tranditional index only with external approximate expression. The index structures of MR-tree and MRD-tree based on multi-approximate expression are set up with the prototype index of R-tree, and the relevant algorithms about the index of insertion, deletion and search are provided. Then, the efficiencies of constructing index based on the multi-approximate expression and window range query are analysised and compared. In addition, the several algorithms and efficiency of soving the maximum enclosed circle and maximum enclosed rectangle are discussed and analyzed during constructing index based on multi-approximate expression.Secondly, the methods and efficiencies are discussed in this paper about the query of direction relationship, distance relationship and distance-direction semi-join based on the multi-approximate index. That is as follosws: 1) The qualitative and quantitative direction query methods based on multi-approximate index are discussed after the direction relationship matrix model and open-shape model are analyzed. And the direction query efficiency based on multi-approximate index is compared with that based on taditional external approximation index. 2) The algorithms of nearest neighbor (NN) and reverse nearest neighbor (RNN) about point, line and ploygen based on multi-approximate index are proposed after the virous methods of distance measure are discussed in detail. And the query efficiency of NN and RNN based on multi-approximate index is compared with that based on taditional external approximation index. 3) The basic concept of semi-join and the strategy of distance-direction semi-join are introduced. And the model of distance relationship, direction relationship and the bounding for spatial object are discussed. Then the method is presented about how to implement the query of distance-direction semi-join, and the efficiency of the algorithm based on multi-approximate index is compared with that based on taditional external approximation index. All the results of these experiments show as follows: The efficiency of construction index based on the multi-approximation is lower than that based on external approximation, but the integrated performance based on multi-approximate index of the query of winsdow scope, direction relationship, distance relationship and distance-direction semi-join is well than that based on external approximate index. Particularly, the advantange based on mulit-approximate index is more obvious when the amount of spatial data is larger.Finally, the research achievements are summarized and directions for further research are pointed out.