Map matching takes the noisy positions a phone or vehicle reports and works out which roads it actually drove. The standard tool is a hidden Markov model (HMM), a probabilistic model in which the unknown road segments form a chain of hidden states and each GPS fix is a noisy observation of one of them. The method works almost perfectly when fixes arrive every few seconds. It fails when they arrive minutes apart, which is exactly how battery-limited trackers and many fleet feeds report. One reported figure puts a classical HMM at 46.46% accuracy on Beijing trajectories sampled every 600 seconds, against 85.39% for a trained diffusion model (DiffMM). Between two fixes ten minutes apart there are many plausible routes. The HMM has only one way to choose among them: it prefers whichever route length best matches the straight-line distance. Nothing in the model knows that drivers concentrate on roads that many trips pass through.
We propose to give the HMM that knowledge without any training data. For every road edge we precompute betweenness, meaning the share of all shortest trips in the city that cross that edge. We then fold it into the transition step, so that routes through high-throughput roads cost less than routes through cul-de-sacs and alleys. Betweenness is not just one more importance score here. If travelers take shortest routes between uniformly random origins and destinations, an edge's betweenness is proportional to the probability that a random trip uses it. It is therefore a route-choice prior derived from the map alone. The question is whether this single unsupervised quantity closes a meaningful part of the gap between classical HMMs and trained neural matchers at low sampling rates. A second question is whether it does so better than the cheap stand-ins a reviewer would reach for: road-class tags and edge popularity counts.
Core Claim
The sparse-sampling failure of HMM map matching is mostly a route-choice failure, not an emission failure. A transition model that scores intermediate routes with a betweenness-derived prior should recover a large share of the lost accuracy at 120 to 600 second intervals. It should keep the HMM's training-free, any-city deployment and its compatibility with exact search pruning, and leave dense-sampling accuracy unchanged. We also make a sharper, falsifiable side claim. Among the centrality families developed for text graphs, the path-based ones (betweenness and coverage) should help on road networks, while the degree-based ones (PageRank, k-core) should not. Road graphs are nearly planar with degree around three to four, so core numbers barely vary and carry little signal.
Relation to Prior Work
The HMM machinery comes from Hidden Markov map matching through noise and sparseness. That paper models emissions as Gaussian in distance-to-road and transitions as exponential in the gap between network distance and straight-line distance. It reports a 0.11% error rate at 30-second sampling on the Seattle benchmark. We keep its emission model unchanged and change only how intermediate routes are scored. Truncating Shortest Path Search for Efficient Map-Matching speeds up the transition computation, by at least 5.4 times at five candidates, with zero accuracy loss. It does this by running one-to-many searches on the reversed graph and cutting off searches that cannot beat the current Viterbi score. It treats all edges uniformly. Our modified edge cost stays nonnegative and additive, so the same truncation still applies; we build on that method rather than compete with it. A novel algorithm of low sampling rate GPS trajectories on map-matching adds speed constraints and reaches above 80% at 1.5 to 2 minute intervals. About 20% of its errors remain at turns, and that is the route-choice regime we target. A Survey on Map-Matching Algorithms motivates the work because it documents accuracy loss in dense grids (Beijing-U, 27.3 km/km²) compared with rural ones (Beijing-R, 13.9 km/km²). It offers no structural remedy.
The neural line replaces the HMM. RNTrajRec learns road representations with graph attention. DiffMM decodes in one diffusion step. Zero-Shot Cellular Trajectory Map Matching treats matching as image translation. That last paper also reports that ID-based learned matchers drop to zero precision in an unseen city, which constrains any learned prior and motivates a map-derived one. We do not claim to beat DiffMM. We use it as an upper reference and ask how much of its advantage an explicit, training-free prior can recover.
On the centrality side, Efficient processing of coverage centrality queries on road networks supplies the computational footing. It computes coverage centrality on DIMACS road graphs and reports 15,444 seconds for global Brandes processing on New York City. That is a one-time offline cost per city, acceptable for a static prior. The text-graph literature supplies the competing centrality families and a cautionary result. TextRank uses PageRank-style voting. A Graph Degeneracy-based Approach to Keyword Extraction shows that k-core methods beat PageRank on word graphs because PageRank over-ranks hub nodes. Map equation centrality scores nodes by how much each contributes to the compressed description of random walks across communities. These papers sharpen an open tension: is "importance" global routing throughput or local cohesion? We expect road matching to side with throughput, and we test this directly instead of assuming it. A Systematic Exploration of Knowledge Graph Alignment with LLMs found that central nodes act as anchors for sequence models. That is weak motivation from a different domain, and nothing in our design depends on it.
Research Program
We precompute, for each directed edge $e$, a betweenness score $b_e$ on the travel-time-weighted road graph. We use exact Brandes on mid-size cities and sampled shortest-path trees on large ones, and we measure how many samples are needed before matching accuracy stops changing. We convert scores to a nonnegative penalty $h_e = -\log(b_e / b_{\max})$, with a small floor so that edges with zero betweenness remain usable. Routes between consecutive candidates $s_i$ and $s_j$ are then found by Dijkstra under the modified cost
$$c(e) = \ell_e \,(1 + \lambda h_e),$$
where $\ell_e$ is edge length and $\lambda \ge 0$ sets the strength of the prior. Setting $\lambda = 0$ recovers the standard HMM exactly. The transition probability keeps the original exponential form in the gap between the chosen route's true length and the straight-line distance. It gains one multiplicative factor, $\exp(-\lambda \sum_{e} \ell_e h_e / L)$, where $L$ is a length normalizer, so that the prior picks the route and also changes how probable that route is. Because the cost is nonnegative and additive, the truncated reverse-graph search applies without change. We will verify empirically that it remains lossless.
The analysis has three parts. First, we break errors down by type: wrong intermediate route, wrong candidate at a fix, or a break in the chain. This tells us whether the gains come from where the theory says they should. Second, we compare centrality families: edge betweenness, coverage centrality, PageRank on the line graph, k-core number, and map equation centrality, all plugged into the same $h_e$ slot. Third, we run a cross-city transfer check in which $\lambda$ is tuned in one city and applied unchanged in another.
Baselines
The naive reference is nearest-road snapping. The literature reports that it hovers around 50% accuracy on sparse taxi data (Liu and Li). It anchors the bottom of every plot.
The primary baseline is the Newson–Krumm HMM itself (Hidden Markov map matching), with Imamichi-style truncation for speed. It is the strongest competitor because our method is this baseline plus one term, so any gain is attributable. For fairness its $\sigma_z$ and $\beta$ get the same validation grid-search budget as our $(\sigma_z, \beta, \lambda)$. This matters because the 46.46% figure reported for HMMs at 600 seconds in DiffMM may reflect an under-tuned implementation. We will report our own tuned number beside it. Beating this baseline means a statistically reliable gain in route-level accuracy at 300 and 600 second intervals, measured over held-out trajectories with bootstrap intervals.
The speed-constrained HMM of Liu and Li is reimplemented and tuned on the same budget. It reports above 80% at 1.5 to 2 minute intervals. We will test whether the prior adds to speed constraints rather than duplicating them.
The upper reference is DiffMM, which reports 85.39% at 600-second sampling in Beijing (DiffMM). DeepMM reaches 68.25% in the same paper. We will not claim to beat DiffMM. Success means closing a stated fraction of the tuned-HMM-to-DiffMM gap with zero training trajectories. We will also run DiffMM in a different-city transfer setting, where trained models are expected to suffer.
Two ablations isolate the key ingredient. The first uses a road-class prior: $h_e$ is set from OpenStreetMap functional class (motorway through residential), tuned on the same grid. The second uses a degree-based prior, either PageRank or k-core, in the same slot. If betweenness does not beat both, the "route-choice" explanation is wrong.
Why not just…?
Why not just use road-class tags as the prior? This is the most serious threat. Functional class is free, and it probably correlates strongly with betweenness. We treat it as a direct competitor and settle the question three ways. We compare the two priors head to head. We check whether their combination beats either alone, which would mean betweenness captures through-routes that class labels miss, such as unclassified connectors that carry cross-town traffic. We also rerun both on maps with tags removed or coarsened, which mimics the poorly tagged maps common outside major cities. If road class matches betweenness everywhere tags exist, we will report that plainly. The contribution then narrows to tag-free maps, plus the finding that the prior works because it encodes route choice.
Why not just count edge popularity from historical trips? If a fleet already has unlabeled history, one can match it with the baseline HMM and use edge visit counts as the prior. This is a learned, data-dependent version of the same idea. We include it as a baseline. We expect it to win once history is plentiful and to suffer in cold-start settings and on rarely traveled edges. We also expect it to inherit the baseline HMM's sparse-sampling errors, since those errors produce its counts. We will plot accuracy against the volume of historical data to find the crossover point. A Bayesian blend that starts at betweenness and shifts toward counts is a natural follow-up if the crossover is early.
Why not just tune the standard HMM or add speed filters? Tuning $\beta$ only reshapes the length-deviation penalty. At 600 seconds, many candidate routes have nearly identical lengths, so no setting of $\beta$ can separate them. Speed filters fail in congestion, when highway and service-road speeds coincide (A Survey on Map-Matching Algorithms). Both are given matched tuning budgets above. The error breakdown will show whether their remaining errors are indeed the route-choice errors the prior targets.
Why not just train a neural matcher? Where paired labels exist in the target city, DiffMM is likely better, and we say so. The case for the prior covers cold start, new cities, and settings that need an interpretable, exactly decoded result. The transfer experiment tests this case directly.
Proposed Experiments
The main experiments use Porto taxi traces (15-second native sampling) and the Beijing sets (60-second native sampling), both downsampled to 60, 120, 300 and 600 seconds as in DiffMM. Ground truth comes from HMM matching at the native dense rate, which is near-exact by the Seattle results. We will hand-audit a sample of these labels to bound label noise. Seattle at 1 Hz (Newson–Krumm) checks that the prior does no harm when sampling is dense: accuracy must stay at the reported near-perfect level. Beijing-U versus Beijing-R tests whether gains grow with road density, as the survey's findings predict. The metrics are point-level accuracy, route-level precision and recall over matched edges, the rate of chain breaks, and runtime with and without truncation.
Three outcomes decide the proposal. The first is whether betweenness beats tuned Newson–Krumm, the road-class prior and the degree-based priors at 300 and 600 seconds. The second is whether the gain is concentrated in wrong-intermediate-route errors and in dense grids. If gains appear evenly across error types, the mechanism is not what we claim. The third is whether a $\lambda$ tuned in Porto transfers to Beijing with little loss, while DiffMM trained in one city degrades in the other. If betweenness fails the first test against road class, the idea collapses to "use tags," and we will report it as such.
References
- DiffMM: Efficient Method for Accurate Noisy and Sparse Trajectory Map Matching via One Step Diffusion
- Hidden Markov map matching through noise and sparseness
- Truncating Shortest Path Search for Efficient Map-Matching
- A novel algorithm of low sampling rate GPS trajectories on map-matching
- A Survey on Map-Matching Algorithms
- RNTrajRec: Road Network Enhanced Trajectory Recovery with Spatial-Temporal Transformer
- Zero-Shot Cellular Trajectory Map Matching
- Efficient processing of coverage centrality queries on road networks
- TextRank: Bringing Order into Text
- A Graph Degeneracy-based Approach to Keyword Extraction
- Map equation centrality: community-aware centrality based on the map equation
- A Systematic Exploration of Knowledge Graph Alignment with Large Language Models in Retrieval Augmented Generation