Building a Ground-Truth Set for Map-Matching Evaluation

Ground truth is the part of validation that teams postpone, because the obvious way to get it — driving planned routes with survey equipment — is expensive enough to need a budget conversation. The result is a matcher that has never been measured.

There is a much cheaper route that gets most of the value. High-rate traces matched generously and reviewed are good enough labels for evaluating the same drives at the fleet’s real sampling rate, and they cost almost nothing per trace. This page sets out that workflow, the review step that makes it trustworthy, and the stratification that stops the resulting set from measuring the easy majority. It supplies the labels the validation topic assumes.

Compatibility and Configuration Requirements

The Labelling Pipeline

from __future__ import annotations

from dataclasses import dataclass, asdict


@dataclass(frozen=True)
class Label:
    trace_id: str
    edges: tuple[tuple[int, int], ...]     # (osm_way_id, direction)
    graph_version: str
    source: str                            # "downsampled" | "instrumented" | "manual"
    reviewed_by: str | None
    network_class: str                     # rural | suburban | urban_grid | dense_centre
    source_rate_hz: float


def candidate_label(trace, matcher_a, matcher_b) -> tuple[Label | None, str]:
    """Match with two configurations; agreement becomes a label, disagreement goes to review."""
    a = matcher_a.match(trace)
    b = matcher_b.match(trace)
    if normalise(a.edges) == normalise(b.edges):
        return Label(
            trace_id=trace.id,
            edges=tuple(normalise(a.edges)),
            graph_version=matcher_a.graph_version,
            source="downsampled",
            reviewed_by=None,
            network_class=classify_network(a),
            source_rate_hz=trace.rate_hz,
        ), "auto"
    return None, "review"

The two-matcher agreement test is what makes this affordable. On a clean 1 Hz corpus two differently-configured matchers agree on ninety to ninety-five percent of traces, and those can be accepted without human time. The remaining five to ten percent are, almost by definition, the interesting ones — parallel carriageways, complex junctions, tunnels — and they are exactly where a reviewer’s attention is worth spending.

Stratifying the Set

An unstratified set inherits the fleet’s own bias. If eighty percent of driving is suburban, eighty percent of the labels will be suburban, and the benchmark will report an accuracy that is essentially the suburban figure — hiding the dense-centre performance that generates most of the complaints.

Sample deliberately instead. A workable target for a mixed fleet:

Then cross that with the sampling rates the fleet actually runs. One reviewed 1 Hz label yields four evaluation traces — 1 Hz, 10 s, 30 s, 60 s — at no extra labelling cost, which makes sampling rate the cheapest axis in the whole exercise to measure.

def downsample_variants(trace, label: Label, rates_s=(1, 10, 30, 60)) -> list[tuple]:
    """One reviewed label, several evaluation traces."""
    return [(trace.every(n), label) for n in rates_s]

Execution and Tuning Guidelines

Record provenance on every label. Which source, which reviewer, which graph version, which date. A label with no provenance cannot be re-examined when the benchmark disagrees with production, and that disagreement is the moment the provenance is needed.

Never overwrite a label. Append a new one and mark the old superseded. Labels are the most expensive artefact in the whole validation exercise, and an accidental overwrite during a re-labelling pass destroys work nobody can reconstruct.

Grow the set from production failures. Every trace that a customer complained about, or that an engineer investigated, should end up in the set. This is what keeps the benchmark representative without a periodic re-labelling project — and it is why the set should be append-only.

Re-resolve labels when the graph moves. Edge identifiers are graph-specific. When the benchmark moves to a newer graph, re-resolve each label’s edges and put any that fail resolution back into the review queue rather than dropping them.

Common Pitfalls Specific to This Technique

Labelling with the same matcher and configuration you are evaluating. The benchmark then measures self-consistency, and every change that makes the matcher more confidently wrong scores as an improvement. The two configurations used for labelling must differ from the one under test.

Treating the review queue as a backlog. Unreviewed disagreements are where the information is. A queue that grows unboundedly means the set is quietly becoming an easy-cases set, which is the failure mode the whole exercise exists to avoid.

Losing the source trace. Keep the raw high-rate recording alongside the label. Without it, a future evaluation at a different sampling rate has to start over, and any question about how the label was derived is unanswerable.

Keeping the Set Alive

A ground-truth set decays in two ways, and both are quiet.

The map moves underneath it. Edge identifiers are graph-specific, and a way that gets split or retagged upstream changes identity. Six months of OSM edits typically invalidates two to five percent of labels in an active urban area. The failure is not an error — the label simply stops matching anything, and the trace silently drops out of the benchmark.

The fleet moves away from it. New depots, new vehicle classes, a change in the sampling-rate mix. The set keeps measuring the fleet as it was when the set was built, and its verdicts drift further from production experience each quarter.

Both are managed the same way: re-resolve on every graph change, and grow the set continuously from production.

def revalidate(labels: list[Label], graph) -> tuple[list[Label], list[Label]]:
    """Split labels into those that still resolve against `graph` and those that do not."""
    live, stale = [], []
    for lab in labels:
        if all(graph.has_edge(way, direction) for way, direction in lab.edges):
            live.append(lab)
        else:
            stale.append(lab)
    return live, stale

Stale labels go back to the review queue, not to the bin. Most of them need only a re-resolution against the new geometry; a few reveal that the road genuinely changed, and those are worth knowing about independently of the benchmark.

Growth from production

The cheapest source of new labels is the work the team already does. Every production trace that somebody investigated — because a customer complained, because a distance looked wrong, because an alert fired — has been effectively hand-reviewed already. Capturing the reviewed edge sequence at that moment costs a few seconds and adds precisely the kind of case a synthetic set will never contain.

Set a target for the mix rather than for the size. A set that is roughly a fifth investigated production cases stays honest; one that is entirely downsampled recordings drifts toward measuring the easy majority, however large it grows.

Related

• Map matching accuracy validation and benchmarking — parent topic
• Measuring map-matching accuracy with Hausdorff and F1 — what to compute against these labels
• Regression testing a map matcher in CI — running the set on every change
• Choosing an interpolation limit for fleet GPS gaps — the same downsample-and-measure method applied upstream
• Trajectory Analysis & Map Matching Techniques — parent section