Research On Trajectory Similarity Search Of Moving Object Based On Road Network

In recent years, with wide use of smart phones and GPS(Global Positioning System) as well as population of Location-Based Services, a large amount of trajectory data has been increasingly getting its accumulation to serve for a variety of applications. At the same time, trajectory data also brings about great challenge on storage, operation, processing and management due to its large scale.Trajectory can be regarded as a track of a moving object with the change of time left in the space. Trajectory similarity search has gradually become a new research hot issue in the database field. In this paper, we consider two types of trajectory search: trajectory spatio-temporal similarity search and trajectory spatial-textual similarity search under the road network. The main work is as follows:(1) A novel algorithm of trajectory spatio-temporal similarity search of moving objects based road network is put forward. The algorithm first uses network Voronoi diagram to divide the network space and pre-computes some necessary network distance. It adopts the two-phase strategy: spatial filtering step and temporal refinement step. In the spatial filtering step, it uses the query point as the center for network Voronoi expansion and then adds the trajectories within the expansion range into the trajectory candidate set; in the temporal refinement step, for every trajectory in the candidate set, it computes the temporal similarity and spatio-temporal similarity. Finally the trajectory with smallest spatio-temporal similarity will be returned as a result.(2) A novel algorithm of trajectory spatial-textual similarity search of moving objects based road network is put forward. The algorithm mainly includes three steps: minimum point matching calculation step, trajectory candidate generation step and trajectory candidate verification step. In the minimum point matching calculation step, it first uses the query point as the center for network expansion, then finds the minimum point match to the trajectory within the expansion and computes the minimum point match distance; in the trajectory candidate generation step, it generates the trajectory candidate set based on the minimum point match distance computed; in the trajectory candidate verification step, for every trajectory in the candidate set, it computes the minimum point set match distance and sorts the trajectories in ascending order according to the distance. Finally the first k trajectories will be returned as a result set.(3) Extensive experiments based on the two algorithms proposed above are performed and verify good effectiveness of the algorithms.