Reconstructing Movement from Sparse Samples: Enhanced Spatio-Temporal Matching Strategies for Low-Frequency Data
Authors: Ali Yousefian, Arianna Burzacchi, Simone Vantini
Organizations: MOX, Department of Mathematics, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133, Milan, Italy · Modeling and Simulation of Socio-Technical Systems, Fondazione Bruno Kessler, Via Sommarive 18, 38123, Trento, Italy
This paper explores potential improvements to the Spatial-Temporal Matching algorithm for aligning the GPS trajectories to road networks. While this algorithm is effective, it presents some limitations in computational efficiency and the accuracy of the results, especially in dense environments with relatively high sampling intervals. To address this, the paper proposes four modifications to the original algorithm: a dynamic buffer, an adaptive observation probability, a redesigned temporal scoring function, and a behavioral analysis to account for the historical mobility patterns. The enhancements are assessed using real-world data from the urban area of Milan, and through newly defined evaluation metrics to be applied in the absence of ground truth. The results of the experiment show significant improvements in performance efficiency and path quality across various metrics.
Figures & tables
Figure 1: Retrieving candidate points and candidate edges for the GPS point pi .
Figure 2: An example of a candidate graph for a 3-point trajectory.
Figure 3: How observation probability changes with distance for different σ values.
Category
Name
Formula
Efficiency
Runtime [seconds]
E1(T)=Tend−Tstart
Average number of candidate points
E2(T)=n1∑mi
Total number of candidate points
E3(T)=∑mi
Quality
Average projection distance [meters]
Q1(T)=n1∑diste(pi,c~i)
Length metric
Q2(T)=∑distn(c~i,c~i−1)∑diste(pi,pi−1)
Complexity ratio
Q3(T)=diste(p1,pn)∑distn(c~i,c~i−1)
Table 1: Evaluation metrics proposed in this study. In the formulations, T is the execution time; S is the set of streets, i.e., grouped edges of the road network; the tilde symbol indicates an optimal variable (e.g., c~i is optimal candidate for the i -th GPS point).
Field
Type
Description
Trajectory ID
categorical
Unique identifier for each individual trajectory
Latitude
numerical
Latitude coordinate of the GPS observation
Longitude
numerical
Longitude coordinate of the GPS observation
Uncertainty
numerical
Radius of a circle around the GPS point with 68% probability
Timestamp
numerical
Date and time at which the GPS point was recorded
Table 2: Main features of the GPS trajectory dataset.
Figure 4: ST-Matching vs. Modified ST-Matching across efficiency metrics.
Figure 5: ST-Matching vs. Modified ST-Matching across matching quality metrics.
Figure 6: ST-Matching vs. Modified ST-Matching across topology metrics.
Figure 7: Comparison of ST-Matching and Modified ST-Matching based on the speed metric.
Figure 8: Comparison of the size of candidate graphs between ST-Matching and Modified ST-Matching (The red line represents the selected matched path).
Figure 9: An example of a reconstructed path for the same trajectory using the two different algorithms.
Figure 10: Edge scores of the road network of Milan.
Figure 11: ST-Matching vs. STB-Matching across efficiency metrics.
Figure 12: ST-Matching vs. STB-Matching across matching quality metrics.
Figure 13: ST-Matching vs. STB-Matching across topology metrics.
Figure 14: Comparison of ST-Matching vs. STB-Matching based on speed metric.
Comparison Outcome
Percentage
Equal overlap with modified ST-Matching
72%
STB-Matching closer to modified ST-Matching
15%
ST-Matching closer to modified ST-Matching
13%
Table 3: Overlap between ST-Matching and STB-Matching using synthetic low-frequency data with the results of the modified ST-Matching on original high-frequency data.
The integration of GNSS data into portable devices has led to the generation of vast amounts of trajectory data, which is crucial for applications such as map-matching. To tackle the limitations of rule-based methods, recent works in deep learning for trajectory-related tasks occur. However, existing models remain challenging due to issues such as the difficulty of large-scale data labeling, ineffective modeling of spatial-temporal relationships, and discrepancies between training and test data distributions. To tackle these challenges, we propose HSTGMatch, a novel model designed to enhance map-matching performance. Our approach involves a two-stage process: hierarchical self-supervised learning and spatial-temporal supervised learning. We introduce a hierarchical trajectory representation, leveraging both grid cells and geographic tuples to capture moving patterns effectively. The model constructs an Adaptive Trajectory Adjacency Graph to dynamically capture spatial relationships, optimizing GATs for improved efficiency. Furthermore, we incorporate a Spatial-Temporal Factor to extract relevant features and employ a decay coefficient to address variations in trajectory length. Our extensive experiments demonstrate the model's superior performance, module effectiveness, and robustness, providing a promising solution for overcoming the existing limitations in map-matching applications. The source code of HSTGMatch is publicly available on GitHub at https://github.com/Nerooo-g/HSTGMatch.
Anjun Gao, Zhenglin Wan, Pingfu Chao +1
School of Computer Science and Technology, Soochow University, Suzhou, China · Metasequoia Intelligence, Shenzhen, China · Department of Astronomy, The Ohio State University, Columbus, OH 43202 USA
Efficient acquisition, storage, and utilization of traffic data are critical challenges in spatio-temporal data management. Most traffic data systems collect and store observations at fixed, coarse-grained temporal intervals to reduce storage and computation costs. However, such coarse-grained data severely limits downstream applications that require predictions at a finer temporal granularity. Collecting and maintaining fine-grained traffic data across all locations and time periods would impose a substantial burden on database storage and preprocessing pipelines. To address this temporal granularity mismatch, we formulate a novel problem: predicting fine-grained future traffic using coarse-grained sampled data. We propose the Spatial-Temporal Refinement Predictor (STRP), a granularity-aware framework for spatio-temporal data systems. STRP integrates two components: Tree Convolution for efficient and interpretable spatial dependency modeling, and Inverse Dilated Convolution for progressive temporal extrapolation. STRP supports two practical prediction settings: window-based and duration-based, to handle different forms of granularity mismatch. Experiments on six benchmark datasets show that STRP significantly outperforms state-of-the-art baselines in both accuracy and efficiency. Our work offers a practical and interpretable approach to managing granularity mismatches in spatio-temporal traffic data systems.
Shuhao Li, Weidong Yang, Yue Cui +4
College of Computer Science and Artificial Intelligence, Fudan University, Shanghai 200082, China · Tongyi Lab, Alibaba Group, Cloud Valley, NO.1008 Dengcai Street, Xihu District, Hangzhou 310020, China · The Hong Kong University of Science and Technology, Hong Kong SAR 999077, China +1
High-quality GPS trajectories are essential for location-based web services and smart city applications, including navigation, ride-sharing and delivery. However, due to low sampling rates and limited infrastructure coverage during data collection, real-world trajectories are often sparse and feature unevenly distributed location points. Recovering these trajectories into dense and continuous forms is essential but challenging, given their complex and irregular spatio-temporal patterns. In this paper, we introduce a novel diffusion model for trajectory recovery named TRACE, which reconstruct dense and continuous trajectories from sparse and incomplete inputs. At the core of TRACE, we propose a State Propagation Diffusion Model (SPDM), which integrates a novel memory mechanism, so that during the denoising process, TRACE can retain and leverage intermediate results from previous steps to effectively reconstruct those hard-to-recover trajectory segments. Extensive experiments on multiple real-world datasets show that TRACE outperforms the state-of-the-art, offering >26% accuracy improvement without significant inference overhead. Our work strengthens the foundation for mobile and web-connected location services, advancing the quality and fairness of data-driven urban applications. Code is available at: https://github.com/JinmingWang/TRACE
Jinming Wang, Hai Wang, Hongkai Wen +2
University of Exeter Department of Computer Science Exeter, United Kingdom · Jingdong Logistics Beijing, China · University of Warwick Department of Computer Science Coventry, United Kingdom