Route Based Map Matching via a Structured Codebook and Token Sequence Decoding
Abstract
This study proposes an efficient and computationally light route based map matching method for GPS track data on urban expressway networks. The key idea is to exploit a symbolic structure of named lines and named junctions that link level map matching leaves unused. We represent each candidate route as a sequence of line and junction names, take the set of such sequences as a route codebook, and formulate map matching as scored alignment of a probe trajectory against members of the codebook. Probes become token sequences via a mesh quantizer, a precomputed grid mapping each coordinate to a line or junction token, and the decoder returns a member of the codebook by construction. The codebook is indexed by a DAFSA × Levenshtein automaton, a fuzzy lookup technique from approximate string matching and speech recognition; the per query decoding cost is orders of magnitude lower than a brute force scan. We evaluate the method on a deformed replica of the Tokyo Metropolitan Expressway topology. The method recovers the exact route at moderate GPS noise and continues to identify the line and junction sequence under heavy noise; a sensitivity analysis maps the mesh resolution operating range. Real probe evaluation, channel model calibration, and a head to head HMM comparison are left to a forthcoming version.
Related
- Structured Masked Diffusion for Shared-Codebook Unsourced Random Access Decoding
- RPA Decoding with Few Subspace Projections for Correcting Structured Error Patterns in RM Codes
- A matching lower bound for the sextic large sieve and structured prime moments
- Bi-Mamba-Load: A bidirectional structured state space model with sequence relationship adaptive perception for electricity load forecasting
- Hierarchical Beam Training and Codebook Design for Movable Antenna-Assisted Near-Field Systems
BibTeX
@misc{sakai2026route,
title = {{Route Based Map Matching via a Structured Codebook and Token Sequence Decoding}},
author = {Takara Sakai and Hiroyuki Hasada},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.22543},
eprint = {2607.22543},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.22543},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Route Based Map Matching via a Structured Codebook and Token Sequence Decoding
AU - Takara Sakai
AU - Hiroyuki Hasada
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2607.22543
UR - https://arxiv.org/abs/2607.22543
AB - This study proposes an efficient and computationally light route based map matching method for GPS track data on urban expressway networks. The key idea is to exploit a symbolic structure of named lines and named junctions that link level map matching leaves unused. We represent each candidate route as a sequence of line and junction names, take the set of such sequences as a route codebook, and formulate map matching as scored alignment of a probe trajectory against members of the codebook. Probes become token sequences via a mesh quantizer, a precomputed grid mapping each coordinate to a line or junction token, and the decoder returns a member of the codebook by construction. The codebook is indexed by a DAFSA × Levenshtein automaton, a fuzzy lookup technique from approximate string matching and speech recognition; the per query decoding cost is orders of magnitude lower than a brute force scan. We evaluate the method on a deformed replica of the Tokyo Metropolitan Expressway topology. The method recovers the exact route at moderate GPS noise and continues to identify the line and junction sequence under heavy noise; a sensitivity analysis maps the mesh resolution operating range. Real probe evaluation, channel model calibration, and a head to head HMM comparison are left to a forthcoming version.
ER -