Fast and synchronized multidimensional similarity measure for trajectories: integrating space, time, and semantic information
Juqing Liu, Jun Li, Ping Jian, Wei Xiong, C.L. Zhang · International Journal of Digital Earth · 2025
While the rich semantic information in trajectories enhances data mining potential, it simultaneously complicates similarity measures. Existing multidimensional similarity methods face two challenges: (1) high computational complexity of O(n × m × k), which limits large-scale applicability, and (2) isolated handling of spatial–temporal-semantic dimensions with inadequate semantic hierarchy modeling. This paper proposes FasMultiSIM, a fast and synchronized multidimensional similarity measure that integrates spatial, temporal, and semantic dimensions. First, a spatiotemporal grid model (rSTGM) is constructed by extending rHEALPix DGGS with temporal dimensions, enabling FasMultiSIM to achieve fast multidimensional similarity computations with time complexity of O((n + m)×k). In addition, FasMultiSIM quantifies hierarchical semantic relationships while preserving the flexibility of semantic tags and enables synchronized multidimensional similarity measures to capture interesting and valuable segments in similar trajectories. Finally, we validated the accuracy and efficiency of FasMultiSIM using both real-world floating cars and social media trajectory datasets. The experimental results demonstrate that FasMultiSIM achieves an approximately one order of magnitude improvement in computational efficiency compared to the state-of-the-art methods, including LCSS, EDR, MSM, and MUITAS. The proposed method is expected to support applications that demand high timeliness and focus on synchronized multidimensional similarity, such as epidemic tracking and personalized intelligent recommendation services.