Reconstructing Movement from Sparse Samples: Enhanced Spatio-Temporal Matching Strategies for Low-Frequency Data

Ali Yousefian; Arianna Burzacchi; Simone Vantini

cs.LGMar 10, 2026

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

Abstract

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 $p_{i}$ .

Figure 2: An example of a candidate graph for a 3-point trajectory.

Figure 3: How observation probability changes with distance for different $\sigma$ values.

Category	Name	Formula
Efficiency	Runtime [seconds]	$E_{1}(T)=\mathcal{T}_{end}-\mathcal{T}_{start}$
	Average number of candidate points	$E_{2}(T)=\frac{1}{n}\sum m_{i}$
	Total number of candidate points	$E_{3}(T)=\sum m_{i}$
Quality	Average projection distance [meters]	$Q_{1}(T)=\frac{1}{n}\sum\text{dist}_{e}(p_{i},\tilde{c}_{i})$
	Length metric	$Q_{2}(T)=\frac{\sum\text{dist}_{e}(p_{i},p_{i-1})}{\sum\text{dist}_{n}(\tilde{c}_{i},\tilde{c}_{i-1})}$
	Complexity ratio	$Q_{3}(T)=\frac{\sum\text{dist}_{n}(\tilde{c}_{i},\tilde{c}_{i-1})}{\text{dist}_{e}(p_{1},p_{n})}$

Table 1: Evaluation metrics proposed in this study. In the formulations,

\mathcal{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.,

\tilde{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).

Panel of Figure 9 — 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.

Map-Based Localization

Map-Based Localization estimates a device or robot’s position and orientation by matching sensor observations to stored maps.

See all 106 papers

Hierarchical Spatial-Temporal Graph-Enhanced Model for Map-Matching
Mar 25, 2026Anjun Gao, Zhenglin Wan, Pingfu Chao +1Spatiotemporal GNNs Trajectory Representation Learning
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
From Coarse to Fine: Managing Temporal Granularity in Spatio-Temporal Data for Fine-Grained Traffic Prediction
Jun 8, 2026Shuhao Li, Weidong Yang, Yue Cui +4Traffic Flow Estimation Spatiotemporal Forecasting
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
TRACE: Trajectory Recovery with State Propagation Diffusion for Urban Mobility
Mar 19, 2026Jinming Wang, Hai Wang, Hongkai Wen +2Trajectory Reconstruction Diffusion Models
University of Exeter Department of Computer Science Exeter, United Kingdom · Jingdong Logistics Beijing, China · University of Warwick Department of Computer Science Coventry, United Kingdom

Mar 25, 2026J/K move · Enter open · S save

Hierarchical Spatial-Temporal Graph-Enhanced Model for Map-Matching

Anjun Gao, Zhenglin Wan, Pingfu Chao, Shunyu Yao

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

Spatiotemporal GNNs Trajectory Representation Learning

Open paper AskPDF arXiv

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.

Abstract

Map-Based Localization

Explore similar work

Hierarchical Spatial-Temporal Graph-Enhanced Model for Map-Matching

From Coarse to Fine: Managing Temporal Granularity in Spatio-Temporal Data for Fine-Grained Traffic Prediction

TRACE: Trajectory Recovery with State Propagation Diffusion for Urban Mobility