Research On Clustering DLIS-R Tree Algorithm Based On Spatial Data

With the development of mobile Internet and Location-Based Services(LBS)applications,the volume of space data is also increasing.The increasing volume of spatial data,however,poses novel problems to traditional indexing mechanisms which usually assume an in-memory index or optimize for local disk access.Therefore,the large-scale spatial data indexing faces new requirements and challenges.The paper takes large-scale data sets as spatial index research objects to optimize the problem of high overlap rate in the most widely used R-tree spatial index structure nodes and low efficiency of large data sets index,the research is mainly discussed from the following parts:Firstly,aiming at the problem of nodes high overlap rate in the traditional R-tree construction process,a K-means clustering algorithm is introduced to reduce the overlap degree of MBR.At the same time,the time efficiency of K-means clustering algorithm in processing large data sets is poor.As the number of data set points increases,the clustering time overhead grows exponentially,which leads to a long construction time of K-means clustering based R-tree.Therefore,this paper introduces the spatial point pattern analysis method to optimize the time efficiency of K-means clustering algorithm.Spatial point model analysis uses zoning statistical methods to distinguish the spatial object distribution pattern,determine the initial centroid,and reduce the number of iterations.This method reduces the build time of K-means clustering based R-trees.Secondly,aiming at the problem of increasing number of geospatial points,the clustering overhead is much larger than the cost of R-tree construction.This paper proposes a two-layered index structure R-tree based on improved K-means clustering(DLIS-R,Double-Layered Index Structure R-tree).The clustering DLIS-R tree uses the X-means clustering algorithm to divide research area into multiple subspaces as the global index,and sets the R-tree index as the local index for the spatial data.The method improves the index efficiency of R-tree by combining global and local indexes.In this paper,the algorithm is programmed with Java language in the Eclipse editor,and tested by multiple sets of data sets.The experimental results show that the clustering DLIS-R tree has a 20% reduction in the overlap ratio compared to the R-tree node,and the highest efficiency improvement is 91.56.%,the lowest is 69.39%,which indicates the clustering-based DLIS-R tree algorithm optimizes the retrieval efficiency of spatial index.