Research On Distributed K-Nearest Neighbors Query Method Over Moving Trajectories

With the rapid development of technologies such as mobile Internet,cloud computing and big data,a large amount of trajectory data is gathered in fields such as transportation,planning and social network.Trajectory data can reflect position change and movement behavior of moving objects in the real world.The purpose of the k-nearest neighbor query over moving trajectories is mainly to find k nearest neighbor trajectory objects of the given query trajectory.Moreover,the k-nearest neighbor trajectory query is widely used in the field of path planning,route recommendation and so on.However,with the rapid increase of the amount of trajectory data,the efficiency and scalability of k-NNT query in traditional centralized environments cannot meet the actual requirements due to the limitation of stand-alone computational resources.Therefore,it is necessary to provide a k-nearest neighbor query method suitable for large-scale trajectory data in a distributed environment.The traditional index of tree structure is not suitable for parallelization due to the hierarchical features.In addition,the index based on Voronoi diagram is difficult to compose and the local index rebuilding efficiency is low when faced with large-scale spatial data.Therefore,a distributed grid index based on MapReduce for trajectory data is designed which splits and partitions the trajectory data into grids under Spark,and trajectory rebuild table is introduced to keep track of the sub-trajectory segments during the query.Then,for the k-nearest neighbor query of large-scale trajectory data,this thesis proposes a processing framework of the k-nearest neighbor trajectory query based on the big data platform Spark.Finally,this thesis combines distributed grid index with MapReduce framework,and proposes the k-nearest neighbor query algorithm,including the distributed grid index-based candidate set generation algorithm and MapReduce-based k-nearest neighbor query algorithm.Experiments and analysis are performed on a Spark cluster with eight nodes.The experimental results show that based on real data sets of different regions,the parallel generation method of grid index proposed in this thesis has good construction efficiency.Furthermore,the k-nearest neighbor trajectory query method based on this index achieves good processing performance and scalability in a distributed environment,which can meet the demand of k-nearest neighbor query on large-scale trajectory data.