Constructing R-tree Spatial Index Based On Dynamic K-value Clustering

With the development of spatial information technology and the increasing needs of location-based services, spatial data management becomes a hotspot in the field of spatial information research. Spatial data is characterized as with massive data, complex structures and strong location correlation. To meet the further growth demand for service quality and speed of spatial retrieval, we need to organize them properly, so that we can efficiently manage, store and analyze spatial data.Index techniques enable quickly locating data when retrieving. R-tree spatial indexes are the current mainstream index technique with simple structure, wide applicability and high dynamic nature. There are three construction methods for R-tree spatial indexes, namely OBO(One by one), preprocessing, and clustering. The OBO method is costly and results in a R-tree with high degree of overlap among its nodes. The preprocessing method reduces the degree of overlap among the nodes and construction complexity, but does not accord with the actual spatial distribution. The clustering method uses clustering algorithms to divide spatial data, which can improve the efficiency of the indexes constructed by organizing a cluster in a sub-tree. However, the current R-tree spatial clustering algorithms use a predefined k-value for clustering, and choose the initial clustering arbitrarily. The clustering results are easily dominated by initial k-value and the outlier data.To alleviate the problem, this thesis surveys the spatial index techniques, takes static spatial data as subject, combines the actual distribution of spatial data, and proposes the Dynamic K-value Spatial Clustering Algorithm, DKSC in short. By choosing an optimized k-value, the algorithm allows the spatial data in the same subspace to be organized into the same sub-tree, and builds an efficient R-tree layer by layer from the root to the leaves. To efficiently insert bulk spatial data, this thesis proposes an auxiliary structure, which makes use of the intermediate results of clustering to improve the efficiency. The experiments conducted with the real datasets generated by Baidu Map API and the simulated datasets show that the proposed DKSC algorithm can build optimized R-tree spatial indexes and improve retrieval efficiency, and the auxiliary structure can improve retrieval efficiency after bulk insertion.