Fast Trajectory Similarity Computation over Road networks

Abstract

With the widespread application of trajectory data in areas such as traffic management and route planning, efficiently computing trajectory similarity for fast retrieval has become a critical challenge. Existing methods for trajectory similarity measurement often face issues of low computational efficiency and poor scalability when dealing with spatiotemporal constraints and complex structural correlations in the data. To address these challenges, we propose a novel Highly Efficient Graph-based Recurrent Unit (HGRU) method for fast trajectory retrieval over road networks. The model connects nodes based on logical associations rather than restricting connections to physical adjacencies. Furthermore, a novel sample construction strategy is introduced, leveraging node adjacency relationships in real trajectory activities to create positive sample trajectories, while generating random non-adjacent negative sample trajectories to enhance model discrimination capability. Then with the help of efficient edge indexing techniques, the node features of the point-fusion graph are processed through a multi-head attention-enhanced graph convolutional network to capture topological information among nodes and construct trajectory embeddings. Subsequently, these trajectory embeddings are processed by a multi-layer gated recurrent unit network, which extracts and integrates deep spatiotemporal features to generate embeddings that accurately represent trajectory similarity. Experimental results on the T-drive and New York datasets demonstrate that our method outperforms existing approaches in trajectory similarity measurement, achieving higher efficiency and accuracy, especially when dealing with incomplete and structurally complex trajectory data, showing exceptional robustness.