Research On Index And Query Methods For Dynamic Spatial Data

Spatial data describes the information of entity objects,such as,the shape and location,and it is widely used in social networks,logistics systems and other systems.With the maturity of computer technology and the growth of the location data collection technology,the scale of location data has increased dramatically,of which the operations of query and retrieval is facing a severe challenge.The problem of spatial data query is one of the hot research topics on the aspect of processing spatial data.There are a lot of mature and efficient algorithms to solve this problem.However,today,in many practical applications,with the changes of spatial data randomly and largely,the classical index structures of spatial data and its methods for query are often unable to give the best solutions to satify the query conditions.In this paper,the problems of the index structure and the query for a large number of dynamic spatial data,which changes randomly,have been studies,and a two layer index structure is proposed for the dynamic spatial data,which is large and changes randomly.And the query methods,such as,range query,KNN query,range approximate query and KNN dynamic query are carried out on the index structure.In the paper,firstly,a two layer index structure is created.In the process of index creation,the local Voronoi graph is generated in every server,and the R tree is generated,which is based on the local Voronoi graph.Therefore,a two layer index structure is created,which is consist of the local Voronoi graph and the R tree,the index structure can be created and updated for the massive,radomly variable dynamic spatial data.Secondly,query algorithms,such as,range query algorithm,KNN algorithm,range approximate query algorithm and KNN dynamic query algorithm,are carried out on the index structure,in which range approximate query algorithm is aimed at an approximate accuracy for the result of the range query during the update of the index.The KNN query is further accurate for the result of the KNN query,when the spatial data is changed during the update of the index,and the results of the query methods are improved.Lastly,the experiments are carried out in the simulated data sets and the real data sets,for the evaluation of the time of the index structure creation,and the performance of the range query algorithm,KNN query algorithm and dynamic query algorithm.The results of the experiment show that the time of index structure creation for spatial data is shorter,and the query algorithms proposed in the paper have better performance and accuracy.