The Research On Technologies Of Voronoi Based Trajectory Search In Road Networks

Mobile Internet and mobile computing has gradually stepped into thousands offamilies, the proliferation of GPS-enable smart devices enable people to log theirgeographical positions and to trace historical movement, the massive trajectory datareflects people’s behavior and social relations. As a kind of widely used technology,trajectory search for multi-locations has become a hot topic issue. The target oftrajectory search for multi-locations is to find the Connected Trajectories from atrajectory dataset, which depends on the connections between trajectories andlocations. At present, the research on searching trajectories by locations is mainlyfocused on European space, without considering the constraint of road networks, andinfluenced by trajectory dataset. The query’s efficiency and extensibility is not goodenough. In order to solve these problems, this paper studies on the technology oftrajectory search for multi-locations in road networks.Firstly, in order to address the impact of trajectory redundancy and heterogeneityon trajectory search, this paper proposes a Voronoi-based trajectory simplificationalgorithm in road networks. Considering the trajectory redundancy and the differentsampling rate in different trajectories, we analyze and summarize the existingtrajectory simplification technology. By taking advantage of Voronoi Diagram, whatis used to pre-compute the distance, and the stable road network structure, we simplifythe mass trajectory dataset, and make it unify the road network node density as roadnetworks semantic trajectory.Secondly, this paper proposes a Voronoi-based connected trajectory searchalgorithm in road networks, aiming at the trajectory search for multi-Locations underthe constraint of road networks. At first, the algorithm uses the neighborhood relationsof Voronoi diagram to transform each query location into the corresponding networknode. Then every node searches trajectories in a given network distance threshold,and to merge all the query results to obtain the trajectories which connectmulti-locations. It not only ensures the limited accessibility of trajectory in networkfor every query location, but also ensures the multi-locations connectivity.Finally, path distance based best-connected trajectory search algorithm is proposed. It introduces the concept of trajectory path distance, and satisfies theapplication requirements of the best-connected trajectory search. The algorithmcomputes the path distance of trajectory which closely connects the query locations,then uses it to measure trajectory connectivity, and ranks the trajectory and outputsbest-connected trajectory. It ensures the best-connected trajectory which is connectedwith multi-locations has the shortest connected path distance.In this paper, we make lots of theoretical research on the above three innovations.We choose the simulation trajectory dataset of the real road networks as theexperiment data. And the experimental results show that the algorithm proposed cansimplify trajectory effectively, especially for the high sampling rate of trajectory data.Voronoi-based connected trajectory search algorithm for multi-locations outperformsthe competitor in performance and scalability. Path distance based best-connectedtrajectory search algorithm also shows a good of performance. The research resultsshow that these algorithms have better application prospect.