Efficient Methods for Accurate Sparse Trajectory Recovery and Map Matching
Preprint
Abstract
Real-world trajectories are often sparse with low-sampling rates (i.e., long intervals between consecutive GPS points) and misaligned with road networks, yet many applications demand high-quality data for optimal performance. To improve data quality with sparse trajectories as input, we systematically study two related research problems: trajectory recovery on road network, which aims to infer missing points to recover high-sampling trajectories, and map matching, which aims to map GPS points to road segments to determine underlying routes. In this paper, we present efficient methods TRMMA and MMA for accurate trajectory recovery and map matching, respectively, where MMA serves as the first step of TRMMA. In MMA, we carefully formulate a classification task to map a GPS point from sparse trajectories to a road segment over a small candidate segment set, rather than the entire road network. We develop techniques in MMA to generate effective embeddings that capture the patterns of GPS data, directional information, and road segments, to accurately align sparse trajectories to routes. For trajectory recovery, TRMMA focuses on the segments in the route returned by MMA to infer missing points with position ratios on road segments, producing high-sampling trajectories efficiently by avoiding evaluation of all road segments. Specifically, in TRMMA, we design a dual-transformer encoding process to cohesively capture latent patterns in trajectories and routes, and an effective decoding technique to sequentially predict the position ratios and road segments of missing points. We conduct extensive experiments to compare TRMMA and MMA with numerous existing methods for trajectory recovery and map matching, respectively, on 4 large real-world datasets. TRMMA and MMA consistently achieve the best result quality, often by a significant margin.Keywords
All Related Versions
- Version 1, 2025-08-14, ArXiv
- Published version: , 363.
This publication has 31 references indexed in Scilit:
- LHMM: A Learning Enhanced HMM Model for Cellular Trajectory Map Matching2023
- Contrastive Trajectory Similarity Learning with Dual-Feature Attention2023
- RNTrajRec: Road Network Enhanced Trajectory Recovery with Spatial-Temporal Transformer2023
- T3S: Effective Representation Learning for Trajectory Similarity Computation2021
- Computing Trajectory Similarity in Linear Time: A Generic Seed-Guided Neural Metric Learning Approach2019
- Deep Representation Learning for Trajectory Similarity Computation2018
- Fast map matching, an algorithm integrating hidden Markov model with precomputationInternational Journal of Geographical Information Science, 2017
- Inferring Uncertain Trajectories from Partial Observations2014
- Reducing Uncertainty of Low-Sampling-Rate Trajectories2012
- STR: a simple and efficient algorithm for R-tree packing2002