Research And Implementation Of Splicing Pattern In Spatiotemporal Trajectory

With the popularity of GPS technology and equipment,different digital devices and background systems are constantly collecting trajectories of the moving objects.It causes the trajectory of one moving object to be stored in different systems.If we can obtain trajectories in these systems,can we identify the trajectories belonging to the same moving object,and then recovered a more complete trajectory of the moving object? For one moving object,the trajectories' IDs in different systems are various so that the trajectory of one moving object can't be recovered from multiple systems by comparing with its IDs.In this thesis,two algorithms of splicing trajectories are proposed to recover the trajectories of moving objects from multiple systems based on the characteristics of distribution of trajectories.One splicing algorithm based on sub-trajectories is proposed for trajectories in which sample points are sparse.Firstly,the algorithm uses a sub-trajectory as a vertex of TrajDAG(Trajectory Directed Acyclic Graph),establishes a directed edge by the splicing conditions of adjacent sub-trajectories,and finds the splicing relations between the trajectories in the process of constructing TrajDAG.Then,the algorithm finds all groups of splicing trajectories by using the splicing relations of trajectories and a listing maximal cliques algorithm.However,the problem of listing maximal cliques is NP-Hard.In order to accelerate the search speed of finding all groups of splicing trajectories,an approximate splicing algorithm is proposed to find all approximate maximal groups of splicing trajectories.The other splicing algorithm based on sample point is proposed for trajectories in which sample points are dense.Firstly,the continuity of trajectory and the density of splicing points are defined by analyzing the distribution of sample points in trajectories.Then the distance between the two trajectories is defined based on the two above definitions.Finally,the groups of splicing trajectories can be found by a algorithm which consists of multiple clustering methods.Experiments show that the two splicing algorithms are adapted to trajectories with different characteristics.The algorithm based on sub-trajectories has better adaptability and better recall rate for trajectories in which sample points are sparse.The algorithm based on point has better adaptability and higher precision rate for trajectories in which sample points are dense.