Abstract: To address the problem of slow similarity query of massive spatio-temporal trajectory data, a similarity query algorithm based on graph structure is proposed. Firstly, the trajectory is modeled as a path with spatial and temporal dimensions in a graph, and a trajectory similarity metric function is designed to match spatial and temporal distances simultaneously. Secondly, based on the similarity metric function, an edge-based inverted index structure combined with time filtering is designed, which supports spatio-temporal similarity query of trajectories while improving query performance using a pruning strategy with distance upper bound. The query algorithm performs distance calculation for each trajectory in the returned set of similar trajectories and sorts to obtain the top k results with the highest similarity. Finally, synthetic dataset and real dataset are used to compare the proposed algorithm with NTrajI algorithm, SHQ algorithm and SHQT algorithm. Experimental results show that the proposed method outperforms the comparison methods in index building and query processing, and obtains higher quality of query results. Therefore, the proposed algorithm is feasible and effective.

Key words: spatio-temporal trajectory, trajectory similarity measure, trajectory similarity search, inverted index, distance bounds