Research Of Hilbert R-Tree Spatial Index Algorithm Base On Improved Clustering Analysis

With the development of information society, Geographic Information System(GIS) and spatial database are widely used in water, evironment,traffic,ocean,land,regional planning and so on.As the key technology of GIS and spatial database, spatial index structure has now already become the very important research topic in the interelated fields at present. Due to the massive increase of spatial data and complexity of itself, it has become the important method to satisfy the needs of constantly increased data indexing and querying by reasonable data orgnization and constructing the high efficient spatial index structure,which is suitable for organization.Firstly, based on the concerning theory of researches on the spatial database and spatial index technology, by the comparison and analysis among the widely used and classic algorithms in the current spatial index structure, the paper does researches on the advantages and deficiencies of those algorithms and makes discussion about direction of improvement and designing ideas of applied algorithms in spatial index.Secondly, according to the limitations and deficiencies of performance in traditional K-means clustering algorithms applied in some fields, an improved K-means clustering algorithm which constructs the high efficient spatial index by clustering analysis, is proposed based on the traditional algorithms. The algorithm has the feature that can determine the cluster amount and center adaptively,it adopts the maximum distance method to choose reasonable cluster centers,and relies on the valid evaluation rules to make sure the amount of more perfect clusters. This algorithm makes the K value be determined more reasonably and the cluster results more stable,which is especially suitable to the clustering of spatial data. Finally, according to the objective existings that spatial objects usually distribute unsymmetrically in most practical problems, if constructing the Hilbert R tree index directly, it will make the area of part of leaf node become bigger and produce the numberous overlap easliy,which leads to the multiple query and thus affects the retrieval efficiency. In order to get better results in processing with these objects, the paper tries to combine the improved K-means clustering algorithm with Hilbert R tree. A Hilbert R tree index algorithm, which introduces the idea of improved K-means algorithm, is proposed based on improved K-means clustering. The idea of improvement is that performs the valid clustering in the inhomogeneously distributed objects before generating trees, and orgnizes the data reasonably based on clustering, produces the leaf nodes and middle nodes according to the interelated rules,then generates the high efficient Hilbert R tree. This algorithm achieves that separated processes with the dense and scattered spatial objects, it makes the area of leaf node smaller and more reasonable assignment,which can solve the problem of cluster storage of adjacent data,decrease the overlaps among the nodes to larger extent,and finally improve the performance of index.