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

Ali Yousefian, Arianna Burzacchi, Simone Vantini · 2026

Read Reconstructing Movement from Sparse Samples: Enhanced Spatio-Temporal Matching Strategies for Low-Frequency Data by Ali Yousefian, Arianna Burzacchi, Simone Vantini (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-09412.txt.

Introduction

Ali Yousefian and colleagues improve the Spatial-Temporal Matching algorithm that aligns GPS trajectories to road networks, focusing on sparse, low-frequency data. The base method works but is slow and less accurate in dense areas with wide sampling gaps. Four changes help: a buffer that adapts in size, an adaptive observation probability, a redesigned temporal score, and behavioral input from past mobility. Tested on real Milan data with new ground-truth-free metrics, the changes lift both speed and path quality.

Catalog record

CREATORAli Yousefian, Arianna Burzacchi, Simone Vantini
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55628
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.09412

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Reconstructing Movement from Sparse Samples: Enhanced Spatio-Temporal Matching Strategies for Low-Frequency Data Ali Yousefian, Arianna Burzacchi, Simone Vantini 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 the 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. Keywords – Data analytics and data science, Traffic networks, Map Matching, GPS data 1 Introduction The widespread use and availability of Global Positioning System (GPS) technologies now enables the continuous monitoring of vehicles and people across both time and space. However, due to intrinsic errors and inaccuracies in positioning systems, raw trajectory data often contain noise, missing segments, and spatial misalignment. Several factors may negatively affect the accuracy of the individual GPS points recorded, such as signal blockage in dense urban environments and inconsistency of GPS receivers. As a consequence, the recorded trajectory may inevitably deviate from the true path taken on the road network [ 5 ] . In addition, by nature, GPS data provide only a partial view of real-world movement: continuous motion is observed only at discrete time intervals, capturing therefore just a subset of the true trajectory. This limitation becomes more pronounced when the data are sampled at low frequency, resulting in large temporal gaps between consecutive observations. In such cases, important details of the trajectory may be lost, making it difficult to precisely reconstruct the true travel path [ 10 ] . To address these limitations, a preprocessing stage is required to facilitate better interpretation of the raw location data, with one of the most essential steps being Map Matching [ 2 ] . The technique is utilized to match the potentially noisy GPS observations of spatial trajectories with their real position on the underlying transportation network, identifying the correct road segment on which a moving vehicle or user travels, and their position on that segment [ 9 ] . It acts as a fundamental step in various location-based applications such as navigation, tracking of vehicles, traffic monitoring, and intelligent transport systems [ 2 , 16 ] . The diversity of road geometries and GPS characteristics has led to a vast landscape of Map Matching algorithms. Literature traditionally categorizes these approaches based on the information they exploit, such as geometric, topological, and probabilistic features [ 5 , 9 , 16 ] , or the underlying computational model, ranging from similarity-based to state-transition and learning-based frameworks [ 2 , 15 ] . However, the effectiveness of these methods is strictly dependent on the sampling frequency of the trajectory data. While geometric and topological methods perform well with high-density data, they often fail in low-frequency scenarios, where the sparse connectivity between points introduces significant ambiguity. Low-frequency data has longer time intervals between two consecutive GPS observations. As cited in [ 5 ] , intervals greater than 30 seconds are considered low-frequency data, and above 2 minutes are ultra-low-frequency data. Statistical analysis in [ 16 ] has shown that in practice there is a large amount of low sampling rate GPS data, typically above the two minute threshold. Low-frequency data make it harder to predict the real route that a moving object has taken since the distance between neighboring GPS points is higher and there might be several different possible paths between them. In this context, one widely cited method for low-frequency GPS data is the ST-Matching, proposed by Lou et al. in 2009 [ 6 ] . This algorithm is a weighted graph technique, i.e., a specific case of state transition models [ 2 ] . Indeed, it forms the matched path based on the weights of a candidate graph, whose nodes represents the point locations on the road map that are candidates for being the true position of the GPS record, and whose edges connect pairs of consecutive points and are weighted based on spatial proximity and a temporal function. As a result, the target becomes finding the longest path on this weighted graph, i.e., the sequence of candidates that maximizes the total weight utility. Despite its effectiveness, the method struggles with complex road topologies, noisy GPS data, and scalability issues when processing large datasets. The goal of our work is to investigate how the ST-Matching algorithm can be improved both in terms of its performance efficiency and the quality of its results. To address this, a set of modified versions of the method is proposed, each designed to overcome specific limitations of the original implementation and enhance the overall performance. In particular, the modified ST-Matching is introduced, refining the original method by improving the candidate point selection method, the spatial analysis component, and the temporal component to better reflect realistic movements, travel time, and speed. Moving on to the realm of low-frequency data, we investigate the potential of adding a behavioral score based on historical data to the algorithm, leading to the design of a new behavioral score and the development of the STB-Matching method. In addition, this paper presents an evaluation framework designed to assess the performance of the modified algorithms. Several metrics are proposed to examine the methods from different perspectives, including computational efficiency, matching accuracy, adherence to topological constraints, and execution speed. Throughout them, a comprehensive comparative analysis is performed to assess the improvements of the new methodologies with respect to the baseline method. The performance and results of thse algorithms are also compared to the baseline on low-frequency data. The proposed approach is validated through a case study in Milan, a key metropolitan area in Northern Italy. The results show clear improvements over the baseline ST-Matching implementation and highlight which modifications are most effective under various operating conditions. The remainder of this paper is organized as follows. Section 2 describes the methodology in detail, including both the baseline and the proposed new algorithms. Section 3 presents the case study application, including the urban area of interest, road network description, data source and structure, and the preprocessing steps used to prepare the dataset. It also presents and discusses the results of the experiment and compares the performance of the algorithms. In the end, Section 4 derives a conclusion and points out potential directions for future work. The implementation of the algorithms and the analysis of the results in this paper are carried out using the programming language Python [ 13 ] . All the code is open source and available in the GitHub repository map-matching [ 14 ] . 2 Methodology 2.1 Prior Definitions Definition (GPS point) . A GPS point p is defined as a combination of the variables of spatial coordinates and the timestamp. Formally, p=(x,y,t) , where x and y are the spatial coordinates,

Read the complete text