Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining · 2022 · 76 citations · 19 references
ComputingData ScienceSpatial AnalysisSpatial Data AnalysisTime Series AnalysisGraph AnalyticsGraph MiningGraph-based LearningMetric LearningTrajectory AnalysisTrajectory PredictionHierarchical Spatial RepresentationSimilarity ComputationSimilarity MetricsSpatial Hierarchical StructureSpatio-temporal Trajectory AnalysisTrajectory MiningTrajectory RepresentationTrajectory Representation Learning
Computing trajectory similarities is a critical and fundamental task for various spatial-temporal applications, such as clustering, prediction, and anomaly detection. Traditional similarity metrics, i.e. DTW and Hausdorff, suffer from quadratic computation complexity, leading to their inability on large-scale data. To solve this problem, many trajectory representation learning techniques are proposed to approximate the metric space while reducing the complexity of similarity computation. Nevertheless, these works are designed based on RNN backend, resulting in a serious performance decline on long trajectories. In this paper, we propose a novel graph-based method, namely TrajGAT, to explicitly model the hierarchical spatial structure and improve the performance of long trajectory similarity computation. TrajGAT consists of two main modules, i.e. , graph construction and trajectory encoding. For graph construction, TrajGAT first employs PR quadtree to build the hierarchical structure of the whole spatial area, and then constructs a graph for each trajectory based on the original records and the leaf nodes of the quadtree. For trajectory encoding, we replace the self-attention in Transformer with graph attention and design an encoder to represent the generated graph trajectory. With these two modules, TrajGAT can capture the long-term dependencies of trajectories while reducing the GPU memory usage of Transformer. Our experiments on two real-life datasets show that TrajGAT not only improves the performance on long trajectories but also outperforms the state-of-the-art methods on mixture trajectories significantly.
19
Heterogeneous Graph Transformer
Ziniu Hu, Yuxiao Dong, Kuansan Wang et al. · 2020 · 1.3K citations · Full text
Seongjun Yun, Minbyul Jeong, Raehyun Kim et al. · arXiv (Cornell University) · 2019 · 515 citations · Full text
Deep Representation Learning for Trajectory Similarity Computation
Xiucheng Li, Kaiqi Zhao, Gao Cong et al. · 2018 · 270 citations
Computing, Geoinformatics, Geospatial Artificial Intelligence +15