Map Matching Accuracy Validation and Benchmarking
Most map-matching work is evaluated by looking at it. Somebody plots a matched trace over a basemap, it follows the roads, and the matcher is declared to work. That method finds catastrophic failures and misses everything else — the reversed one-way segment, the parallel service road, the junction where the path takes the wrong exit and rejoins two hundred metres later.
Those are the failures that matter, because they are the ones that reach a distance report or a driver’s scorecard while looking entirely plausible. Catching them needs ground truth, metrics that see different kinds of wrongness, and a gate that runs on every change. This page covers all three, and connects to the algorithm choices described in choosing a map matching algorithm.
Prerequisites
- A matcher you can run repeatedly and deterministically. If the same input can produce two different outputs, measure that first — a non-deterministic matcher cannot be benchmarked.
- Ground truth, discussed at length below. This is the part that takes work.
- A projected CRS for every distance computation, per coordinate reference system mapping.
- A pinned graph version, so a change in accuracy can be attributed to the matcher rather than to the map — see pinning map versions.
shapely2.0+ andnumpyfor the geometric metrics.
What Ground Truth Means Here
Ground truth for map matching is a sequence of edge identifiers, not a line on a map. That distinction matters: two matchers can produce visually identical lines while disagreeing about which carriageway of a dual carriageway the vehicle was on, and only an edge sequence records the difference.
There are three practical sources, in descending order of cost and quality.
Instrumented drives. A vehicle with a survey-grade receiver, driven on a planned route, with the route recorded independently. Expensive per trace and unimpeachable. A few dozen of these anchor everything else.
High-rate recordings downsampled. Take 1 Hz traces, match them with generous parameters and a careful review, treat that as truth, then downsample to the fleet’s real rate and evaluate against it. This is the workhorse: it costs almost nothing per trace and it directly measures the effect of the sampling rate, which is usually the dominant factor.
Manually labelled production traces. Somebody walks a trace through a map and records the edge sequence. Slow and error-prone at scale, but it is the only source for the awkward cases — the multi-storey car park, the private yard, the ferry — and those are exactly what a benchmark drawn from easy traces will miss.
Metrics That See Different Failures
No single metric covers map matching, because there are three independent ways to be wrong: in position, in topology, and in time.
| Metric | What it measures | Blind to |
|---|---|---|
| Hausdorff distance | Worst-case geometric deviation | Direction, topology, missing links |
| Correct-edge rate | Share of distance on the right edge | How far wrong the wrong ones were |
| Edge F1 | Precision and recall over the edge set | Ordering and direction |
| Temporal alignment error | Timing along the matched path | Purely geometric errors |
| Route-length error | Total distance, matched against truth | Compensating errors in both directions |
The pairing that covers the most ground for the least effort is correct-edge rate plus temporal alignment error. The first catches wrong roads; the second catches right roads traversed in the wrong order or the wrong direction, which the first cannot see at all.
Route-length error deserves a warning. It is the metric a business asks for, and it is the easiest to be accidentally right on: a match that takes a wrong turn and a compensating wrong turn back can have almost exactly the correct total distance while being wrong the whole way. Report it, but never gate on it alone.
Stratifying the Result
A single fleet-wide accuracy figure is close to useless, because it is dominated by whichever combination of network and sampling rate happens to be most common. Stratify by two axes at minimum:
- Network density — rural, suburban, urban grid, dense centre. This is where the algorithm choice shows up.
- Sampling interval — 1 Hz, 10 s, 30 s, 60 s and above. This is usually the larger effect, and it is a hardware and cost question rather than a software one.
A stratified table answers questions a single number cannot: whether to spend on better trackers or on a better matcher, which depots need attention, and whether a proposed change helps everywhere or trades one stratum against another. That last case is common enough to be worth watching for — a parameter change that improves dense-urban accuracy by three points while losing two on rural traces is a different decision depending on where the fleet drives.
Gating Changes
Once the benchmark exists, wire it into continuous integration. The gate has three properties worth insisting on.
It fails on a regression beyond a tolerance, not on any change. Matching accuracy moves slightly with any change to candidate search or tie-breaking, and a zero-tolerance gate gets disabled.
It reports per stratum, not just in aggregate. A change that loses four points on 60-second traces while gaining one overall should be visible as what it is.
It runs against a pinned graph. Otherwise a map refresh will show up as a code regression, and the team will spend a day looking in the wrong place.
def gate(new: dict[str, float], baseline: dict[str, float], tol_pts: float = 0.5) -> None:
regressions = {
k: (new[k] - baseline[k]) * 100
for k in baseline
if (new[k] - baseline[k]) * 100 < -tol_pts
}
if regressions:
raise SystemExit(f"accuracy regression beyond {tol_pts} pts: {regressions}")Watching for Drift in Production
The benchmark protects against changes you make. It does not protect against changes made to you — a map refresh, a device firmware rollout that alters the sampling rate, a new operating area with different network characteristics.
For those, track the same metrics on live traffic. Full ground truth is unavailable there, but two proxies work well: the share of traces that fail to match at all, and the distribution of the matcher’s own confidence. Neither measures correctness, and both move sharply when something upstream changes — which is exactly what a drift alarm needs to do.
Frequently Asked Questions
Is the matcher’s confidence score a substitute for ground truth?
No, and the reason is worth being precise about. A confidence score measures how well the observations fit the path the matcher already selected. A trace snapped confidently onto a parallel service road produces a high score, because the fixes really are close to that road and the transitions really are cheap. Confidence measures internal consistency, not correctness, and the two diverge exactly where matching is hard. Use it to triage which traces deserve a human look, never as a label.
How do I evaluate a matcher when no ground truth exists for a region?
Use agreement between independent matchers as a weak proxy, and be explicit that it is one. Where two differently-configured engines agree, the match is probably right; where they disagree, something is hard. That gives a usable ranking of traces to investigate without giving an accuracy figure. It is enough to find problems and not enough to publish a number, and conflating the two is the most common misuse of the technique.
What accuracy should a fleet actually expect?
On 1 Hz urban traces against a current graph, ninety to ninety-five percent correct-edge rate is realistic. At 30-second reporting the same fleet typically sits in the high seventies to mid eighties in dense centres and the low nineties on trunk roads. Numbers above ninety-eight percent on urban data almost always mean the evaluation set is easier than production — check how the labels were made before treating it as a target.
Should accuracy be reported per vehicle or per trace?
Per trace for engineering, per vehicle for operations. Engineering needs the trace-level distribution to find failure modes; operations needs to know which vehicles produce unreliable data, which is a hardware and installation question. The two views frequently disagree, and that disagreement is informative: a handful of vehicles producing most of the bad traces is a very different problem from uniform mediocrity.
How does sampling rate compare with algorithm choice as a driver of accuracy?
Sampling rate usually wins, and by a wide margin. Moving a fleet from 60-second to 10-second reporting typically buys more accuracy than any algorithmic change available, because it removes ambiguity rather than resolving it more cleverly. That makes the benchmark a procurement input as much as an engineering one — the stratified table is the argument for or against better hardware.
What is the minimum viable version of this whole exercise?
Fifty labelled traces spread across your two hardest network types, correct-edge rate and temporal error, run manually before each release. That is an afternoon of work and it catches the regressions that reach customers. Everything else on this page is refinement on top of it, and a team that has the minimum version running is in a far better position than one still planning the full one.
Operational Troubleshooting
Benchmark accuracy is far above production experience. The suite is drawn from easy traces. Add the awkward cases: multi-storey car parks, private yards, ferry crossings, and anything a driver has complained about.
Accuracy moves every run without any change. The matcher is non-deterministic — usually an unordered candidate set or a tie broken by dictionary ordering. Fix that before trusting any number.
One stratum swings wildly between runs. It is too small. A stratum with thirty traces has a standard error of several points; either grow it or stop reporting it separately.
A change improves the benchmark and worsens production. The suite has drifted from the workload. Check when it was last extended, and whether the fleet’s sampling-rate mix has moved since.
Deployment Checklist
Benchmarking Engines Against Each Other
The same apparatus answers a second question: which engine to run. Published comparisons are of limited use here, because match accuracy depends far more on your network and your sampling rate than on the engine’s algorithm — all three mainstream engines implement the same hidden-Markov idea.
Run the comparison on your own stratified set, against the same graph data, and report the same metrics. Two practical notes make the result meaningful.
Normalise the output before comparing. Each engine returns its own edge identifiers, so both sides must be resolved to OSM way identifiers plus a direction flag first. Skipping this measures the identifier scheme rather than the match, and it is the single most common error in engine comparisons.
Give each engine a fair configuration. A default-configured Valhalla against a carefully tuned OSRM measures the tuning. Spend the same effort on each: set each engine’s emission and transition parameters from the same measured receiver error, and use the same candidate radius policy.
The result is usually less dramatic than expected. Correct-edge rate typically differs by two to four points across engines on the same data, while latency and operational cost differ by an order of magnitude — which is why choosing a routing engine argues the decision is usually made on constraints rather than on accuracy.
Where an engine does lose materially, the loss is almost always concentrated in one stratum, and the stratified report shows which. That is a more useful finding than a headline number: it may mean the engine is a good fit for the trunk-road majority and a poor one for the city-centre work, which suggests running two rather than choosing one.
Related
- Building a ground-truth set for map-matching evaluation — how to assemble the labels this page assumes
- Measuring map-matching accuracy with Hausdorff and F1 — the metric implementations
- Regression testing a map matcher in CI — wiring the gate up
- Detecting map-matching drift after an OSM update — the production-side watch
- Trajectory Analysis & Map Matching Techniques — parent section