Detecting and classifying gaps in trajectory streams

A gap is not one thing. A device in power-save, a vehicle in a tunnel, a network outage, a failing antenna, a clock step and a trip that simply ended all produce the same symptom — no fixes for a while — and each needs a different fill policy. Classifying them costs a few columns of context and turns the fill decision from a judgement call into a lookup.

Why this happens

The elapsed interval alone carries almost no information about cause. A four-minute gap could be a tunnel, a coffee break or a dropped connection, and the correct treatment differs: interpolate through the tunnel, split at the break, and interpolate-with-uncertainty through the dropout. Choosing one policy for all gaps means being wrong about two-thirds of them.

What does discriminate is the context either side. A tunnel gap ends with the vehicle moving at roughly the speed it entered at, displaced along a plausible road. A power-save gap ends where it began. A device fault is preceded by degrading fix quality. A clock step has a negative or implausibly small interval rather than a large one. Each signature is cheap to compute from columns you already have, and the treatment ladder they feed is in gap filling in sparse trajectories.

Only the last column is a decision. Everything to its left is arithmetic on columns the pipeline already carries, which is what makes automatic classification worth building.

Core pipeline

Establish the expected cadence per device, because a “gap” is only a gap relative to what that device normally does.
Measure the context — displacement across the gap, speed either side, and fix quality before it.
Classify by signature, in an order that puts the unambiguous cases first.
Emit the class, not just the duration, so the fill policy downstream is a lookup rather than a judgement.

Production-ready Python implementation

PYTHON

import numpy as np
import pandas as pd


def classify_gaps(
    df: pd.DataFrame,
    time_col: str = "t",
    x_col: str = "x",
    y_col: str = "y",
    speed_col: str = "speed_ms",
    quality_col: str | None = "hdop",
    entity_col: str = "entity_id",
    cadence_multiple: float = 4.0,
    stationary_m: float = 40.0,
    trip_end_s: float = 900.0,
) -> pd.DataFrame:
    """
    Label every gap in a trajectory with its likely cause.

    Parameters
    ----------
    cadence_multiple : float
        A gap is an interval longer than this times the device's OWN median
        interval. An absolute threshold mislabels every slow-reporting device
        as permanently gappy.
    stationary_m : float
        Displacement below which the vehicle is treated as not having moved.
        Set it above positional error, or noise across a long gap reads as
        movement.

    Returns
    -------
    pd.DataFrame
        One row per gap: entity, start, end, duration, displacement, class.

    Raises
    ------
    ValueError
        On missing columns or an empty frame.
    """
    required = {time_col, x_col, y_col, speed_col, entity_col}
    missing = required - set(df.columns)
    if missing:
        raise ValueError(f"Missing required columns: {missing}")
    if df.empty:
        raise ValueError("Input DataFrame is empty.")

    rows = []
    for ent, g in df.sort_values([entity_col, time_col]).groupby(entity_col, sort=False):
        t = g[time_col].to_numpy()
        dt = np.r_[np.nan, np.diff(t).astype("timedelta64[ns]").astype(float) / 1e9]
        median_dt = np.nanmedian(dt[dt > 0]) if np.any(dt > 0) else np.nan
        if not np.isfinite(median_dt) or median_dt <= 0:
            continue                       # cannot define a gap without a cadence

        threshold = median_dt * cadence_multiple
        x, y = g[x_col].to_numpy(), g[y_col].to_numpy()
        v = g[speed_col].to_numpy()
        q = g[quality_col].to_numpy() if quality_col in g else np.full(len(g), np.nan)

        for i in np.flatnonzero((dt > threshold) | (dt <= 0)):
            disp = float(np.hypot(x[i] - x[i - 1], y[i] - y[i - 1]))
            gap_s = float(dt[i])
            v_before, v_after = float(v[i - 1]), float(v[i])
            # Quality trend over the five fixes before the gap.
            q_trend = float(np.nanmean(q[max(i - 5, 0):i]) - np.nanmean(q[max(i - 12, 0):max(i - 5, 1)])) \
                if np.isfinite(q).any() else np.nan

            # Order matters: the unambiguous signatures are tested first, so
            # an ambiguous case falls through to the most conservative label.
            if gap_s <= 0:
                kind = "clock_step"
            elif q_trend > 1.5:
                kind = "device_fault"
            elif disp < stationary_m and gap_s >= trip_end_s:
                kind = "end_of_trip"
            elif disp < stationary_m:
                kind = "power_save"
            elif abs(disp - v_before * gap_s) < 0.35 * max(disp, 1.0) and v_before > 5.0:
                kind = "tunnel"
            else:
                kind = "network_outage"

            rows.append({
                entity_col: ent, "gap_start": t[i - 1], "gap_end": t[i],
                "duration_s": gap_s, "displacement_m": disp,
                "v_before_ms": v_before, "v_after_ms": v_after,
                "quality_trend": q_trend, "gap_class": kind,
            })

    return pd.DataFrame(rows)

Validation block

PYTHON

def validate_gap_classes(gaps: pd.DataFrame, total_fixes: int) -> dict:
    """Sanity checks on the classification before a fill policy uses it."""
    if gaps.empty:
        return {"gaps": 0}

    counts = gaps["gap_class"].value_counts(normalize=True).to_dict()

    # 1. Clock steps should be rare. A high rate is a device problem, not a
    #    gap problem, and no fill policy addresses it.
    assert counts.get("clock_step", 0) < 0.05, (
        f"{counts['clock_step']:.0%} of gaps are clock steps — fix the clocks "
        "before filling anything"
    )

    # 2. Tunnel classification requires movement; a zero-displacement tunnel
    #    means the signature test is inverted.
    tunnels = gaps[gaps["gap_class"] == "tunnel"]
    if len(tunnels):
        assert (tunnels["displacement_m"] > 0).all(), "tunnel gap with no displacement"

    # 3. The unclassified fallback must not dominate. If most gaps land in
    #    network_outage, the signatures are not discriminating.
    assert counts.get("network_outage", 0) < 0.6, (
        f"{counts['network_outage']:.0%} fell through to the fallback — the "
        "signatures are not separating these gaps"
    )

    # 4. Gap rate per fix, as an operational metric.
    rate = len(gaps) / max(total_fixes, 1)
    return {"gaps": len(gaps), "gaps_per_fix": rate, "class_mix": counts}

The power-save mode's sharp edge is a firmware setting and is often the easiest class to confirm. Everything else needs the displacement and speed context.

The per-device median is one groupby and it removes the entire class of bug where a slow-reporting population is reported as chronically unreliable.

Common mistakes and gotchas

An absolute gap threshold. A device reporting every ninety seconds is not permanently gappy. Derive the threshold from each device’s own median interval.
Filling before classifying. Interpolating through an end-of-trip gap manufactures a journey between two days’ work.
Ignoring the quality trend. Rising HDOP before a gap is the clearest device-fault signal available and it costs one rolling mean.
Treating a clock step as a gap. The interval is negative or tiny, not large; a gap detector keyed only on “long interval” misses it entirely.
A stationary threshold below positional error. Noise across a ten-minute gap then reads as movement, and a parked vehicle is classified as a tunnel.
Not recording the class. Once the gap is filled, the reason is unrecoverable, and every downstream dwell or distance metric silently mixes real and inferred movement.

FAQ

How long is a gap?

Relative to the device: four times its own median interval is a good default. That makes a 1 Hz device gappy at four seconds and a 30-second device gappy at two minutes, which is what “unexpectedly missing” means in each case.

What if I have no quality column?

The classification still works with displacement and speed alone; only the device-fault class becomes undetectable, and those gaps fall into network_outage. Recording HDOP and satellite count is cheap and worth it — see using HDOP and satellite count to weight GPS fixes.

Should classification run in the stream or in batch?

Batch, or at least with a lookahead, because the class depends on what happens after the gap as well as before. A streaming implementation can emit a provisional class on the first fix after the gap and revise it once a few more arrive, which is the same buffering pattern used elsewhere in streaming window processing.

Gap Filling in Sparse Trajectories — the parent reference and the treatment ladder these classes select from.
Interpolating Missing GPS Points with Kalman Filters — the fill method for the classes that permit filling.
Segmenting Trips by Dwell Time and Gap Thresholds — the consumer that turns a gap into a trip boundary.
Flagging Impossible Jumps and Teleports in GPS Feeds — the clock-step case in more detail.
Time-Series Synchronization Strategies — the clock work that removes one whole class from this list.

Back to Gap Filling in Sparse Trajectories