RouteMatching

Choosing an Interpolation Limit for Fleet GPS Gaps

Every resampler needs a number: the longest gap it is allowed to fill. Most pipelines inherit that number from whoever wrote the first version, and it survives untested for years while the fleet, the hardware and the operating area all change around it. This page replaces the guess with a measurement you can rerun whenever any of those change.

The method is a downsampling experiment. Take traces you already have at a high rate, delete blocks of known length, fill them the way production would, and measure how wrong the fill was. The output is a curve of error against gap length that is specific to your roads and your vehicles, and reading a limit off it takes about a minute. It extends the policy discussion in trace resampling and densification with the experiment that settles it.

Compatibility and Configuration Requirements

Requirement Value Notes
Reference corpus ≥ 200 vehicle-hours at 1 Hz Fewer than that and the tail of the error distribution is noise
Coverage Same operating area and vehicle classes as the target fleet A limit derived on motorway data will not survive a city round
Corpus quality Outliers already removed A spike inside a synthetic gap makes the error look like an interpolation failure
CRS Projected, metres Errors are measured in metres; degrees make the numbers latitude-dependent
numpy ≥ 1.26 Vectorised gap generation

The reference corpus does not have to be large, but it does have to be representative. Borrowing an open 1 Hz dataset recorded in a different city will produce a beautifully smooth curve that says nothing about your junction spacing.

The Experiment

from __future__ import annotations

import numpy as np
import pandas as pd


def gap_error_curve(
    trace: pd.DataFrame,
    gap_lengths_s: tuple[int, ...] = (10, 20, 30, 45, 60, 90, 120, 180, 300),
    trials_per_length: int = 200,
    rng: np.random.Generator | None = None,
) -> pd.DataFrame:
    """Measure interpolation error against gap length on a 1 Hz reference trace.

    ``trace`` must be 1 Hz, sorted, and carry projected ``x``/``y`` columns in
    metres. Returns one row per gap length with median and p95 error.
    """
    rng = rng or np.random.default_rng(20260806)
    x = trace["x"].to_numpy()
    y = trace["y"].to_numpy()
    n = len(x)
    rows = []

    for gap in gap_lengths_s:
        if n < gap + 4:
            continue
        errs = []
        starts = rng.integers(1, n - gap - 2, size=trials_per_length)
        for s in starts:
            e = s + gap                      # first index kept after the gap
            # Linear fill between the bracketing survivors, exactly as production would.
            t = np.arange(1, gap + 1) / (gap + 1)
            fx = x[s - 1] + t * (x[e] - x[s - 1])
            fy = y[s - 1] + t * (y[e] - y[s - 1])
            d = np.hypot(fx - x[s:e], fy - y[s:e])
            errs.append(d)
        allerr = np.concatenate(errs)
        rows.append(
            {
                "gap_s": gap,
                "median_m": float(np.median(allerr)),
                "p95_m": float(np.percentile(allerr, 95)),
                "max_m": float(allerr.max()),
                "samples": int(allerr.size),
            }
        )
    return pd.DataFrame(rows)

The function deliberately reproduces production’s fill rather than a cleverer one. If the pipeline interpolates linearly, the experiment must interpolate linearly — measuring the error of a spline the pipeline does not use tells you nothing about the pipeline.

One trial: remove a block, fill it, measure the error A 1 Hz reference trace turns through a junction. A 45-second block is removed and replaced with a straight line between the bracketing fixes. The largest error occurs mid-gap, where the true path was around the corner and the fill cuts across it. One trial at gap = 45 s peak error 34 m last kept fix first kept fix solid line: the 1 Hz truth · dashed: what the fill would have produced Repeat with random start points across the corpus so the curve reflects how often gaps land on turns, not just that they can. Straight sections contribute near-zero error and pull the median down — which is why the p95 matters as much as the median.

Execution and Tuning Guidelines

Run the curve per road class if you have one, and per operating area if you do not:

curves = (
    reference.groupby("road_class", group_keys=True)
    .apply(lambda g: gap_error_curve(g))
    .reset_index(level=0)
)

Pick the error budget before looking at the curve. The budget comes from the consumer, not from the data. If matched output feeds a geofence dwell detector with 50-metre polygons, an interpolation error of 40 metres is already changing answers. If it feeds a weekly utilisation report, 200 metres is invisible. Deciding the budget afterwards turns the exercise into a justification of whatever number you already had.

Read the limit off the p95, not the median. The median is dominated by straight sections where interpolation is nearly free. The p95 is dominated by the junctions, which is where the errors that change downstream answers actually live.

Expect the limit to differ by a factor of three or more across road classes. That is not noise; it is the geometry. A motorway gap of three minutes hides one gentle curve, while an urban gap of forty-five seconds can hide two right turns and a roundabout.

Reading the limit off the curve Median and 95th-percentile interpolation error plotted against gap length for an urban corpus. A horizontal line marks a 50-metre error budget. The median crosses it at about 110 seconds and the 95th percentile at about 40 seconds, so a limit set on the median would be nearly three times too generous. Urban corpus, 640 vehicle-hours, linear fill 200 m 100 m 0 50 m error budget median p95 40 s 110 s 10 s 300 s Set the limit at 40 s here. A limit of 110 s meets the budget on average and misses it on one gap in twenty. One gap in twenty, across a fleet-month, is thousands of segments — enough to be visible in any report that sums distance.

Common Pitfalls Specific to This Technique

Running the experiment on the fleet’s own low-rate data. You cannot measure interpolation error without knowing where the vehicle actually was, which means the corpus has to be higher-rate than the feed you are setting the limit for. If no 1 Hz data exists, instrument a handful of vehicles for a week; it is cheaper than the alternative of guessing.

Sampling gap start points uniformly over the trace. Real gaps are not uniform — they cluster in tunnels, urban canyons and multi-storey car parks, which are exactly the places where the vehicle is also turning. A uniform sample understates the error. If you can, sample start points from the observed gap-start distribution of the real feed instead.

Setting one limit and never revisiting it. The limit is a function of the fleet’s hardware, the network it drives on, and the error budget of the consumers. All three move. Re-run the curve when a device family changes, when the operating area expands, and whenever a new consumer with a tighter budget appears.

Turning the Curve Into a Configuration

The curve is only useful if it becomes a value the pipeline reads. Three patterns work, in increasing order of effort and of accuracy.

A single constant. One limit for the whole fleet, derived from the tightest error budget among the consumers. Simple, auditable, and wasteful — it forces motorway traces to obey an urban limit and therefore leaves coverage on the table for the majority of driving that is not in a city.

A per-road-class table. Two or three values keyed on the matched road class of the fix preceding the gap. This captures most of the available accuracy for very little complexity, and it is the option worth reaching for first. The class is already present after map matching, so the only cost is the lookup.

GAP_LIMIT_S = {
    "motorway": 180,
    "trunk": 120,
    "primary": 90,
    "residential": 45,
    "service": 30,
}
DEFAULT_GAP_LIMIT_S = 45          # unmatched fixes get the strictest value

A per-fix budget. Compute the plausible displacement from the last known speed and the gap duration, and refuse the fill when it exceeds the error budget directly. This is the most accurate approach and the hardest to explain to somebody reading a report six months later, which is a real cost rather than a rhetorical one.

Whichever pattern you choose, write the limit that was applied onto the row. A filled point whose limit is unknown cannot be re-evaluated when the budget changes, and re-deriving it from the configuration in force at the time is an archaeology exercise nobody completes.

Re-running the experiment

Schedule the curve as a quarterly job rather than a one-off. It should be re-run whenever a device family changes its reporting rate, whenever the operating area expands into a materially different network, and whenever a new consumer arrives with a tighter budget than the existing ones. Each of those moves the answer, and none of them announces itself in a way the pipeline would notice.

Store each run’s output with the corpus it was measured on. A limit is a claim about a specific fleet on a specific network, and the evidence for it should be recoverable — otherwise the next person to ask “why 45 seconds?” gets the same shrug that prompted this page.

Three ways to hold the limit A single constant retains the least coverage for a given error budget but is trivial to audit. A per-road-class table recovers most of the available coverage for modest effort. A per-fix speed-based budget recovers slightly more again and is materially harder to explain. Coverage retained at a fixed 50 m error budget single constant 71 % · trivial to audit per road class 89 % · a five-row table per-fix budget 93 % · hard to explain The middle option captures four fifths of the available gain for a configuration change rather than a code change. The last four points are rarely worth a rule that cannot be explained to whoever signs off the distance report. Whichever is chosen, store the applied limit per row so the decision can be revisited without re-deriving it.

Related

Up to section Trace Resampling and Densification for Fleet GPS Related Resampling GPS Traces to a Fixed Interval in pandas Related Snapping Irregular Fixes to a Common Time Grid with Polars Related Douglas-Peucker Simplification for Fleet Trace Storage Related Deduplicating Repeated GPS Fixes from Buffered Trackers