Map Matching & Network Snapping for Synthetic Traces

Most consumers of movement data join it to a network before doing anything else: a road segment, a rail link, a corridor identifier. That join is map-matching, and it happens whether or not the producer performs it. This page is part of Trajectory & Movement Simulation, and it covers the property a synthetic trace needs in order to survive it — matchability — along with the argument for shipping unsnapped coordinates and a separately versioned match.

The failure this stage prevents is subtle. A trace whose coordinates are individually plausible can still be systematically unmatchable: sitting between two parallel carriageways, crossing a junction through a turn no legal manoeuvre allows, or drifting far enough from the network that a matcher assigns it to a service road it never used. None of that is visible in a positional-accuracy check.

Problem Framing: Matchability Is a Property of the Pair

A matcher balances two costs. The emission cost is how far a fix is from a candidate segment; the transition cost is how implausible the movement between consecutive candidates is, given the network’s connectivity and turn restrictions. A match is the sequence of segments minimising their sum.

That structure produces three distinct ways a synthetic trace fails:

Emission-dominated failure. The noise model is too wide, so the correct segment is not the nearest one, and the matcher picks a neighbour. This is the failure teams expect, and it is the least common of the three.

Transition-dominated failure. The trace is close enough to the right segments and moves between them in a way the network forbids — a turn that does not exist, an entry against a one-way, a jump between carriageways with no crossing point. The matcher rejects the low-emission path because its transition cost is infinite, and returns something worse. This is the most common failure and it originates in the routing stage rather than in the noise model.

Ambiguity failure. Two candidates are equally plausible on both costs — parallel carriageways, a service road beside a main road, a footway alongside a street. The matcher picks one, sometimes flipping between them along the trace, and the result is a match that is unstable rather than wrong.

Map-matching outcomes by dominating cost, with the originating stage for each A single horizontal bar spans all three thousand simulated matches, divided into four segments. The largest segment is the traces that matched cleanly. Of the failures, the largest share is transition-dominated: the trace was close enough to the right segments and moved between them in a way the network forbids, so the matcher rejected the low-emission path and returned something worse. Beside it the annotation records where that originates — the routing stage, two stages upstream of the noise model. The next share is ambiguity: two candidates equally plausible on both costs, typically parallel carriageways or a service road beside a main road, where the match is unstable rather than wrong; that originates in the network's own geometry and cannot be tuned away. The smallest failure share is emission-dominated — the noise model wide enough that the nearest segment is not the correct one — and it is annotated as the one teams actually tune. The point the annotations make together is that the parameter most often adjusted addresses the least common failure, while the most common one is fixed by making the generator consult turn restrictions. The parameter teams tune addresses the least common failure 20% 12% 64% transition (illegal manoeuvre) — 20% originates in: the routing stage — two stages upstream ambiguity (parallel candidates) — 12% originates in: the network's own geometry emission (noise too wide) — 4% originates in: the noise model — the one teams tune matched cleanly — 64% 3,000 simulated matches, fixed seed. The most common failure is fixed by making the generator consult turn restrictions; the least common is the one the emission sigma controls.
Measured over 3,000 simulated matches: the failure teams tune for is the least common, and the most common one originates two stages upstream.

Prerequisites & Toolchain

networkx==3.3
shapely==2.0.4
numpy==1.26.4

The prerequisite that is not a package is a network with turn restrictions and one-way flags actually populated. A matcher given a graph with no restrictions cannot produce a transition-dominated failure at all, which sounds convenient and means the trace has not been tested against the thing that will reject it in production.

Core Concept: The Hidden Markov Formulation

The standard matcher is a hidden Markov model. Segments are hidden states, fixes are observations, the emission probability falls with distance from the segment, and the transition probability falls as the network distance between two candidates diverges from the straight-line distance the agent actually travelled.

python
import math


def emission_logp(dist_m: float, sigma_m: float = 12.0) -> float:
    """Log-probability that a fix this far from a segment came from it."""
    return -0.5 * (dist_m / sigma_m) ** 2 - math.log(sigma_m)


def transition_logp(route_m: float, straight_m: float, beta_m: float = 30.0) -> float:
    """Penalise routes much longer than the straight line between two fixes.

    An impossible move — no path, or a forbidden turn — has no route distance at all,
    and returns negative infinity rather than a large penalty, because a matcher that
    merely dislikes illegal turns will still take one when the alternative is worse.
    """
    if route_m is None or not math.isfinite(route_m):
        return -math.inf
    return -abs(route_m - straight_m) / beta_m

The -inf rather than a large negative number is the detail that matters for generation. A matcher that treats an illegal turn as expensive rather than impossible will produce a match through it when the alternative is bad enough, and a synthetic trace that relies on that leniency will match against a permissive matcher and fail against a strict one.

Emission-side and transition-side match failures against the matcher's sigma The horizontal axis is the emission sigma the matcher assumes, in metres, from three to fifty. Three curves share a percentage axis. The falling curve is transition-side failure: with a tight sigma, fixes that are legitimately a little off the segment fall outside the matcher's tolerance, the correct candidate is never considered, and the matcher is forced onto a path with a worse transition cost. The rising curve is emission-side failure: with a wide sigma, more candidates become plausible and the nearest one stops being reliably the correct one. Their sum, drawn heavier, has a shallow interior minimum which is marked, and the word shallow is doing work — the total barely improves across a wide band of sigma, which is why tuning it feels unproductive. The note underneath states what the shape means in practice: sigma is not the lever people hope it is, and the way to move the whole curve down rather than slide along it is to generate legal paths in the first place, which removes the transition-side failures at their source instead of trading them for emission-side ones. Sigma slides along the curve; legal paths move the whole curve down 5 10 20 30 40 50 0% 20% 40% 60% 80% matcher emission sigma (m) traces failing to match (%) shallow minimum at σ ≈ 18 m transition-side emission-side total failures transition-side emission-side 2,400 simulated traces per sigma, fixed seed. The minimum is shallow, which is why tuning sigma feels unproductive: it trades one failure mode for the other. Generating legal paths removes the transition-side failures at their source and moves the whole curve down.
The two costs on the same axes: widening the noise model moves failures from one regime into the other rather than removing them.

Step-by-Step Implementation

Step 1 — Generate along the network, with restrictions applied

The single most effective thing a generator can do for matchability is to produce paths that are legal on the network in the first place. That means the routing stage — Markov routing or otherwise — must consult turn restrictions, not only connectivity.

python
def legal_successors(graph, prev_edge, node) -> list:
    """Edges leaving `node` that may legally be entered from `prev_edge`."""
    banned = graph.nodes[node].get("no_turn", {}).get(prev_edge, set())
    return [e for e in graph.edges(node, keys=True)
            if e not in banned and not graph.edges[e].get("oneway_against", False)]

A generator without this produces traces that are individually plausible and collectively unmatchable, and no amount of noise tuning downstream will fix them.

Step 2 — Perturb after routing, in a metric frame, at a scale the matcher tolerates

Noise is applied to a legal path rather than used to create one. The scale is the decision: too small and the trace is unrealistically clean, too large and the emission term starts choosing wrong segments.

python
def perturb(path_xy, rng, sigma_m=8.0, rho=0.93):
    """Correlated lateral error, which is what a receiver actually produces."""
    out, e = [], 0.0
    for (x, y), (nx_, ny) in zip(path_xy, path_xy[1:] + path_xy[-1:]):
        e = rho * e + math.sqrt(1 - rho ** 2) * rng.normal(0, sigma_m)
        dx, dy = nx_ - x, ny - y
        ln = math.hypot(dx, dy) or 1.0
        out.append((x - dy / ln * e, y + dx / ln * e))       # lateral, not isotropic
    return out

Perturbing laterally rather than isotropically is worth the extra lines. Real positional error relative to a road is dominated by the across-track component, and an isotropic model puts as much error along the road as across it — which matters because along-track error is nearly free for a matcher and across-track error is what causes mismatches.

Step 3 — Match, and keep the confidence

python
def match(trace, graph, k=6):
    """Viterbi over the k nearest candidate segments per fix."""
    best = viterbi(trace, graph, k=k)
    return {
        "segments": best.path,
        "score": best.logp / max(len(trace), 1),      # per-fix, so traces compare
        "runner_up_margin": best.logp - best.second_logp,
        "unmatched_fixes": best.unmatched,
    }

The runner_up_margin is the field worth carrying forward. A match with a large margin is a match the matcher is confident in; a small margin means a second interpretation was nearly as good, which is the signature of the ambiguity failure and the thing a consumer should be told about rather than left to discover.

Step 4 — Ship the trace unsnapped, and the match beside it

python
release = {
    "trace": unsnapped_fixes,                 # what the receiver would have produced
    "match": {                                # optional, separately versioned
        "network_version": "osm-2026-07-01",
        "matcher": "hmm/1.4",
        "sigma_m": 12.0,
        "results": matches,                   # with per-trace score and margin
    },
}

Snapping before release is lossy in three ways: it discards the off-network portion of the movement, it commits to one matcher’s interpretation of ambiguous geometry, and it makes the release depend on a network version that will change. Publishing both lets a consumer who disagrees redo the match, and a consumer who needs the raw movement still have it.

Validation & Testing

python
def test_generated_paths_are_legal(paths, graph):
    """Every consecutive edge pair must be a permitted manoeuvre."""
    for path in paths:
        for prev, nxt in zip(path, path[1:]):
            node = shared_node(prev, nxt, graph)
            assert nxt in legal_successors(graph, prev, node), (prev, nxt)


def test_match_recovers_the_generated_path(traces, graph, min_iou=0.95):
    """The matcher should recover the path the generator actually used."""
    for t in traces:
        got = set(match(t["fixes"], graph)["segments"])
        want = set(t["path"])
        iou = len(got & want) / len(got | want)
        assert iou >= min_iou, f"IoU {iou:.2f}"


def test_ambiguity_is_reported_not_hidden(traces, graph, min_margin=2.0):
    low = [t for t in traces if match(t["fixes"], graph)["runner_up_margin"] < min_margin]
    assert len(low) / len(traces) < 0.05, f"{len(low)} traces are ambiguous"
Three release shapes for matched movement data, by capability and by how they age Three rows. Shipping snapped coordinates only gives a consumer a segment identifier immediately and nothing else; the raw movement, the off-network portion and any disagreement with the match are irrecoverable, and the release ages badly because it is bound to a network version that will change under it. Shipping unsnapped coordinates only preserves everything and makes every consumer do their own matching, which is work they may do inconsistently; nothing is irrecoverable, and the release ages well because it makes no claim about a network. Shipping both — unsnapped coordinates plus a match carrying its own network version, matcher version, parameters and per-trace confidence — gives the immediate answer to consumers who want it and leaves the evidence for those who disagree; nothing is irrecoverable, and the release ages well because the match can be superseded without republishing the trace. A footer names the property that makes the third row work: the match is a derived artifact with its own version, so it can be corrected, re-run against a newer network, or withdrawn, without touching the movement data underneath it. The match is a derived artifact — version it like one Release shape a consumer can… irrecoverable how it ages snapped only join to a network immediately raw movement, off-network portion, disagreement badly — bound to a network version unsnapped only everything, after doing their own match nothing well — it claims nothing about a network unsnapped + versioned match both, and audit the match nothing well — the match supersedes independently A versioned match can be corrected, re-run, or withdrawn on its own. None of those require republishing the movement underneath it — which is the whole reason to keep the two artifacts separate. Consumers who need a segment on every row get a derived view with a fallback flag, not a destroyed distinction.
The match is a derived artifact; versioning it separately lets it be corrected without republishing the trace.

The second test is the round trip, and it is the one that gives this stage a ground truth the other derived quantities lack: the generator knows which segments it routed along, so the match can be scored exactly rather than approximately.

Performance & Scale Considerations

Viterbi over k candidates per fix costs k² transition evaluations per step, and each transition evaluation is a shortest-path query on the network. That product is what makes matching expensive, and two things control it. Keeping k small — four to six is usually enough — cuts the quadratic term. Caching route distances between candidate pairs cuts the expensive part, and the cache hits often, because consecutive fixes share candidates.

For a release-scale validation, match a stratified sample rather than every trace. Stratify by area type — dense urban, arterial, rural — because matchability varies far more between those than within them, and a uniform sample will be dominated by whichever type has the most traces.

Matching Is Not Snapping, and the Difference Matters

The two words are used interchangeably and they name different operations with different failure modes, which is worth separating before a release note has to explain itself.

Snapping moves a coordinate onto a geometry. It is per-fix, it has no memory, and its only input is distance. Snapping a trace means moving every fix to its nearest segment, which produces a result that is locally plausible and globally incoherent: consecutive fixes can snap to segments that do not connect, and the “route” that results is not a route at all.

Matching assigns a sequence of fixes to a path. It has memory, its input includes the network’s connectivity and restrictions, and its output is a legal route rather than a set of independent assignments. Everything on this page is about matching, and the distinction is why: almost every failure described here is invisible to snapping, because snapping never asks whether the sequence it produced could have been travelled.

The practical consequence is in what a release claims. A release that says its traces are “snapped” is claiming much less than one that says they are “matched”, and a consumer who reads the first and expects the second will find that consecutive fixes jump between unconnected segments. If the pipeline performs snapping — and for some purposes that is entirely reasonable — say so, and do not describe the output as a route.

There is a third operation worth naming because it is often what a consumer actually wants: conflation, which reconciles two representations of the same network rather than placing observations on one. It appears in this area whenever a release is regenerated against an updated network, and it is a different problem again.

Failure Modes & Troubleshooting

  • Matches flip between parallel carriageways along a single trace. Ambiguity, and it is usually a symptom of isotropic noise. Lateral-only perturbation plus a transition term that penalises carriageway changes without a crossing point resolves most of it.
  • Matching fails at junctions specifically. A turn restriction the generator ignored and the matcher enforces. Check the generated path’s legality before blaming the noise.
  • The matcher assigns traces to service roads. The emission sigma is wider than the separation between the main road and the service road. Either tighten the noise or accept that this particular geometry is unmatchable at this accuracy — and say so.
  • Match quality is fine on a sample and poor in production. The sample was not stratified. Rural traces match easily and dominate a uniform sample.
  • The match is perfect and consumers still complain. They are matching against a different network version. This is the argument for shipping the network version with the match rather than the match alone.

Cost, and Where It Actually Goes

Matching is the most expensive validation in this area, and the cost is concentrated somewhere unintuitive, which is worth knowing before optimising the wrong thing.

The Viterbi recursion itself is cheap. What is expensive is the transition term, because evaluating it requires a shortest-path query between two candidate segments, and with k candidates per fix there are k² such queries per step. For a trace of a few hundred fixes with six candidates each that is tens of thousands of routing queries, and it dominates everything else by an order of magnitude.

Three things control it, in descending order of effect. Reducing k cuts the cost quadratically, and four to six candidates is almost always enough — a seventh candidate is essentially never the answer, and keeping it multiplies the work by a third. Caching route distances between candidate pairs helps far more than it sounds, because consecutive fixes share most of their candidate sets, so the same pair is queried repeatedly within a single trace. Bounding the search radius for the routing query at a small multiple of the straight-line distance stops the router exploring the whole network when two candidates are genuinely unconnected, which is the pathological case that makes a small number of traces take longer than all the others combined.

For release-scale validation, none of that is a substitute for sampling. Match a stratified sample — by area type, because matchability varies far more between dense urban and rural traces than within either — and report the per-stratum scores rather than a pooled number. A uniform sample will be dominated by whichever stratum has the most traces, which is usually the one that matches easily.

Frequently Asked Questions

Should synthetic traces be snapped before release?

Usually not. Snapping discards the off-network movement, commits to one interpretation of ambiguous geometry, and binds the release to a network version. Ship unsnapped coordinates plus, if consumers want it, a separately versioned match carrying its own confidence score — so a consumer who disagrees with the match can redo it and one who needs raw movement still has it.

What about movement that genuinely leaves the network?

Car parks, pedestrian areas, fields, private land: real traces contain plenty of it, and a synthetic release that never leaves the network is detectable on that alone. Generate it deliberately, flag it, and expect the matcher to leave those fixes unmatched — a matcher that assigns every fix to a segment is a matcher that will assign a car park to whichever road happens to be nearest.

Does map-matching leak anything about the source data?

The match itself does not, because it is a function of the trace and a public network. What can leak is the choice of network: a release matched against a proprietary or internally-corrected network discloses something about that network’s content wherever the match differs from what a public one would produce. If the network is sensitive, publish the match against a public network or not at all.

How often should the match be regenerated?

Whenever the network version it names is superseded, and not otherwise. Because the match is a separately versioned artifact, regenerating it is cheap and touches nothing else — the trace stays exactly as published and only the derived layer moves. Consumers who pinned the old match keep working; consumers who resolve the latest get the new one.