# Efficient Methods for Accurate Sparse Trajectory Recovery and Map Matching

arXiv: https://arxiv.org/abs/2508.10460 · HTML: https://mlsanity.com/paper/2508.10460/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 14 Aug 2025.

## Builds on (most cited first, 11 of 11)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Contrastive Trajectory Similarity Learning with Dual-Feature Attention](https://mlsanity.com/paper/2210.05155/) (2022)
- [Deep Spatially and Temporally Aware Similarity Computation for Road Network Constrained Trajectories](https://mlsanity.com/paper/2112.09339/) (2021)
- [RNTrajRec: Road Network Enhanced Trajectory Recovery with Spatial-Temporal Transformer](https://mlsanity.com/paper/2211.13234/) (2022)
- [AttnMove: History Enhanced Trajectory Recovery via Attentional Network](https://mlsanity.com/paper/2101.00646/) (2021)
- [Micro-Macro Spatial-Temporal Graph-based Encoder-Decoder for Map-Constrained Trajectory Recovery](https://mlsanity.com/paper/2404.19141/) (2024)
- [Modelling of Bi-directional Spatio-Temporal Dependence and Users' Dynamic Preferences for Missing POI Check-in Identification](https://mlsanity.com/paper/2112.15285/) (2021)
- [Inferring Uncertain Trajectories from Partial Observations](https://mlsanity.com/paper/1603.07641/) (2016)
- [Efficient Non-Learning Similar Subtrajectory Search](https://mlsanity.com/paper/2307.10082/) (2023)

## Abstract (arXiv)

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.