SST: Synchronized Spatial-Temporal Trajectory Similarity Search

The volume of trajectory data has become tremendously large in recent years. How to effectively and efficiently search similar trajectories has become an important task. Firstly, to measure the similarity between a trajectory and a query, literature works compute spatial similarity and temporal similarity independently, and next sum the two weighted similarities. Thus, two trajectories with high spatial similarity and low temporal similarity will have the same overall similarity with another two trajectories with low spatial similarity and high temporal similarity. To overcome this issue, we propose to measure the similarity by synchronously matching the spatial distance against temporal distance. Secondly, given this new similarity measurement, to overcome the challenge of searching top-k similar trajectories over a huge trajectory database with non-trivial number of query points, we propose to efficiently answer the top-k similarity search by following two techniques: trajectory database grid indexing and query partitioning. The performance of our proposed algorithms is studied in extensive experiments based on two real data sets.