Detecting Map-Matching Drift After an OSM Update

The fitness gate in front of graph promotion catches the large failures — a truncated extract, a broken build. It runs on a sample with a tolerance, which means it is structurally blind to the failure that matters most in practice: a regression concentrated in one small area.

A vandalised junction, a mis-tagged one-way system or a bridge deleted by an over-enthusiastic editor affects the vehicles that drive there and nobody else. Across a fleet sample it is a fraction of a point, comfortably inside any tolerance. For the depot whose vehicles use that junction every day, it is a step change.

This page covers the production-side monitors that catch that case, all of which run on data the pipeline already produces.

Compatibility and Configuration Requirements

Three Monitors

Unmatched rate

The share of traces that fail to produce a match at all. Cheapest to compute, earliest to move, and the least ambiguous — a trace that cannot be matched is a trace whose road no longer exists in the graph, or whose network has been severed.

SELECT depot_id,
       date_trunc('day', enter_utc) AS day,
       count(*) FILTER (WHERE osm_way_id IS NULL)::float / count(*) AS unmatched_rate
FROM matched_fixes
WHERE enter_utc >= now() - interval '30 days'
GROUP BY 1, 2;

Confidence distribution

The matcher’s own confidence is useless as an accuracy measure and excellent as a change detector. Its absolute level says little; a shift in the shape of its histogram says something upstream moved. Compare the current day’s distribution against a trailing baseline with a simple divergence measure and alert on the number, not on the mean.

Edge churn

Re-match a fixed sample of recent traces against both the outgoing and incoming graph, and count how many edge sequences differ. This is the most direct measure of what a promotion actually did, and it is the only one that attributes a change to the map rather than to the traffic.

def edge_churn(sample, graph_old, graph_new) -> dict:
    changed = 0
    for trace in sample:
        a = match(graph_old, trace).edges
        b = match(graph_new, trace).edges
        if a != b:
            changed += 1
    return {"n": len(sample), "changed": changed, "share": changed / len(sample)}

Attributing a Change to the Map

A monitor that fires tells you something changed. Separating a map cause from a data cause takes one more step, and it is worth automating because the two lead to completely different investigations.

The discriminator is whether the same input behaves differently. Keep a shadow sample — a few hundred traces from the previous week — and re-match it against the new graph on every promotion. If the shadow sample’s match quality drops, the map changed. If the shadow sample is stable and live traffic degrades, the input changed: a firmware rollout, a new device family, a depot that started operating somewhere new.

def attribute(shadow_delta_pts: float, live_delta_pts: float) -> str:
    """Which side of the pipeline moved?"""
    if shadow_delta_pts < -0.5 and live_delta_pts < -0.5:
        return "map"                 # fixed input, worse result
    if shadow_delta_pts > -0.5 and live_delta_pts < -0.5:
        return "input"               # same map, worse traces
    return "neither"

That two-line rule removes most of the guesswork from an incident. Without it, the standard response to a quality alert is to look at the matcher, which is the component least likely to have changed.

Turning a Detection Into a Fix

Once a promotion is identified as the cause, the localisation is usually quick because the damage is geographic. Aggregate the newly-unmatched fixes by a coarse spatial grid and the affected area falls out immediately — typically a handful of cells, often one.

SELECT ST_SnapToGrid(geom, 500) AS cell, count(*) AS newly_unmatched
FROM matched_fixes
WHERE graph_version = :new_version
  AND osm_way_id IS NULL
  AND enter_utc >= :promotion_time
GROUP BY 1
ORDER BY 2 DESC
LIMIT 20;

From there the response is one of three, in increasing order of effort. Roll back if the damage is material and the cause is not obvious — the previous graph is on disk and the swap takes seconds. Fix upstream if OpenStreetMap is genuinely wrong; a corrected edit propagates to every future rebuild and to everyone else using the data. Overlay locally if the map is right and your fleet’s situation is special, using the mechanism in adding truck restrictions.

Whichever path is taken, record the cell and the cause. Over a year these accumulate into a map of where your operating area is fragile — usually new-build industrial estates and recently-remodelled junctions — and that list is worth watching proactively rather than reactively.

Common Pitfalls Specific to This Technique

Alerting on the fleet mean. The whole point of these monitors is that map damage is local. A mean across depots is the one aggregation guaranteed to hide it.

Comparing across a period when the input also changed. A device rollout in the same week as a promotion makes attribution impossible unless the shadow sample is in place. Run the shadow re-match on every promotion, not only when something looks wrong.

Treating a confidence drop as an accuracy measurement. It is a change detector. Reporting a confidence shift as “accuracy fell by four points” is a claim the signal cannot support and will be contradicted the first time somebody labels the traces.

Running the Monitors Cheaply

None of these monitors needs a dedicated pipeline. Each one is a query over data the matcher already writes, and the total cost is a few minutes of compute a day.

Unmatched rate is an aggregate over the output table, partitioned by day and depot. On a partitioned store it reads one day’s partition and finishes in seconds.

Confidence distribution is a histogram over the same partition, stored as a small daily row so the comparison against a trailing baseline is a join rather than a re-scan.

Edge churn is the only one that costs real compute, because it re-matches. Keeping the shadow sample to a few hundred traces bounds it at a couple of minutes, and there is no benefit to a larger sample — the signal is a share, and a few hundred traces measures a share to well within the precision the decision needs.

def daily_monitors(day: str) -> dict:
    return {
        "unmatched_by_depot": unmatched_rate(day),          # seconds
        "confidence_hist": confidence_histogram(day),        # seconds
        "edge_churn": edge_churn(shadow_sample(), old, new), # ~2 minutes, promotion days only
    }

Run the first two daily and the third only on promotion days. Churn between two identical graphs is zero by construction, so computing it on non-promotion days is pure waste.

Storing the history

Keep the daily aggregates indefinitely; they are tiny and they are what makes a step change visible. A year of per-depot unmatched rates is a few thousand rows, and the first time somebody asks “has this always been like that?” the answer is a query rather than an opinion.

The same series is what allows a threshold to be set from evidence. A depot whose unmatched rate has sat between 0.3 and 0.6 percent for a year has an obvious alert threshold; one with no history has a threshold somebody guessed.

Related

• Map matching accuracy validation and benchmarking — parent topic
• Scheduling OSM extract refreshes for routing engines — the promotion these monitors watch
• Pinning map versions for reproducible fleet matching — the version stamp every monitor here depends on
• Regression testing a map matcher in CI — the pre-merge counterpart to these production checks
• Trajectory Analysis & Map Matching Techniques — parent section