Deduplicating Driver Position Pings Before Reverse Geocoding

TL;DR: Most position pings cannot produce a different address from the one before them, so looking them up is pure waste. Filter on movement first, collapse dwell periods to a single representative ping, and sample long stationary stretches on a timer. A vectorised implementation and its tuning are below; the surrounding workflow is reverse geocoding workflows in Python.

Where the Redundancy Comes From

A vehicle’s day is mostly not movement. Loading, unloading, breaks, traffic and overnight parking all produce long runs of near-identical coordinates, and each one is a separate billable reverse lookup if nothing filters them. Understanding the shape of the redundancy is what makes the thresholds obvious rather than arbitrary.

Where a day's position reports actually occur A timeline of one vehicle day divided into segments. Overnight parking, a depot load, several delivery stops and a lunch break are stationary segments that together account for most reports. Driving segments account for far fewer reports but nearly all of the distinct addresses. One vehicle, 24 h, one report every 30 s — 2 880 reports overnight parked drive depot load break shaded = stationary · solid = moving Stationary segments ≈ 76% of reports · ≈ 12 distinct addresses one lookup each is sufficient; the rest add nothing Moving segments ≈ 24% of reports · most distinct addresses still highly redundant at street precision

The asymmetry in the lower panel is the whole opportunity. Three quarters of the reports describe a dozen places, and a filter that recognises this removes most of the cost without losing a single distinct answer.

The Vectorised Filter

from __future__ import annotations

import numpy as np
import pandas as pd

EARTH_M = 6_371_000.0


def _haversine_m(lat1, lon1, lat2, lon2):
    """Vectorised great-circle distance in metres between paired arrays."""
    p1, p2 = np.radians(lat1), np.radians(lat2)
    dphi = p2 - p1
    dlam = np.radians(lon2 - lon1)
    h = np.sin(dphi / 2.0) ** 2 + np.cos(p1) * np.cos(p2) * np.sin(dlam / 2.0) ** 2
    return 2.0 * EARTH_M * np.arcsin(np.sqrt(h))


def compress_pings(
    df: pd.DataFrame,
    *,
    move_m: float = 60.0,
    max_gap_s: float = 900.0,
) -> pd.DataFrame:
    """Keep pings that moved beyond `move_m`, plus one per `max_gap_s` while stationary.

    Expects columns: device_id, lat, lon, ts (epoch seconds).
    """
    df = df.sort_values(["device_id", "ts"], kind="mergesort").reset_index(drop=True)

    keep = np.zeros(len(df), dtype=bool)
    for _device, idx in df.groupby("device_id", sort=False).indices.items():
        lat = df["lat"].to_numpy()[idx]
        lon = df["lon"].to_numpy()[idx]
        ts = df["ts"].to_numpy()[idx]

        anchor = 0
        keep[idx[0]] = True
        for i in range(1, len(idx)):
            moved = _haversine_m(lat[anchor], lon[anchor], lat[i], lon[i])
            waited = ts[i] - ts[anchor]
            if moved >= move_m or waited >= max_gap_s:
                keep[idx[i]] = True
                anchor = i
    return df.loc[keep].reset_index(drop=True)

The loop is per device rather than per row, and the distance maths is vectorised inside it, which keeps a million-ping day in the low seconds. A fully vectorised version is possible with a cumulative-anchor trick, and is rarely worth the loss of readability — the anchor must be reset on each kept ping, which is inherently sequential.

Why an Anchor Rather Than a Neighbour Comparison

The obvious implementation compares each ping to the one before it, and it is subtly wrong: a vehicle creeping forward five metres at a time never triggers the threshold and never gets looked up at all, no matter how far it eventually travels.

Neighbour comparison versus anchor comparison A vehicle moves in a series of small five-metre steps along a road. Under neighbour comparison each step is below the sixty-metre threshold so no ping is ever kept. Under anchor comparison the distance is measured from the last kept ping, so a ping is kept once the cumulative movement reaches the threshold. neighbour comparison — each step measured from the last ping nothing kept — 400 m travelled anchor comparison — measured from the last KEPT ping kept every 60 m of travel

The same reasoning applies to GPS jitter in the opposite direction. A stationary vehicle whose fix wanders a few metres produces a neighbour distance that is nonzero on every report; measuring from a fixed anchor keeps it below the threshold and correctly emits nothing.

Choosing the Two Thresholds

Setting Effect of lowering Effect of raising Start from
move_m more lookups, finer track fewer lookups, risk of missing a stop the precision target: 60 m for street, 25 m for building
max_gap_s more lookups during dwells long dwells lose their timeline 15 minutes for activity reporting

The time threshold exists because a stationary vehicle still generates useful information: knowing a driver was at one address from 09:00 to 11:30 requires a ping in the middle, not just at the ends. Fifteen minutes gives a usable timeline at a small fraction of the raw volume.

Measuring the Compression

Emit the ratio, not just the counts. Kept pings over raw pings is a single number that summarises device behaviour, and it moves for reasons worth knowing about: a fleet-wide firmware update that changes report frequency, a new depot where vehicles idle longer, a tracker with a failing GPS chip producing jitter that defeats the anchor.

A stable ratio also validates the thresholds. If compression sits at 78% for months and then drops to 40% with no change in fleet size, either the vehicles are genuinely moving more or something upstream is injecting noise — and the reverse-geocoding bill will follow within a day.

Validating That Nothing Useful Was Lost

Compression is only safe if it discards pings whose answer would have matched. That is a testable claim, and testing it once on a sample is worth more than any amount of reasoning about thresholds.

Take a day of raw pings for a handful of representative devices, resolve every one of them without compression, then resolve the compressed set and compare. The metric that matters is the share of raw pings whose address differs from the address of the kept ping that represents them. On a well-chosen threshold that share is a fraction of a percent, and the records where it differs are almost always at a genuine boundary.

Repeat the exercise per environment rather than once globally. A dense city centre and a rural delivery round have different address densities, and a threshold that loses nothing in one may lose real distinctions in the other. The output of the exercise is not a single number but a small table of thresholds by area type, which is exactly the shape the rest of this pipeline already uses for tolerances.

The comparison is also a useful regression test to keep. Running it monthly against a fixed sample catches the case where a tracker firmware change alters reporting behaviour enough that the old threshold no longer means what it did — a change that is otherwise invisible until someone questions a route report.

Edge Cases and Failure Modes

Out-of-order pings. Mobile networks deliver reports late and out of sequence. Sorting by timestamp per device before filtering is not optional; an unsorted stream produces anchors that jump backwards and keeps far more pings than it should.

Device identifier reuse. A tracker moved from one vehicle to another appears as an impossible jump. Include a trip or assignment identifier in the grouping key where one exists, so the anchor resets at the handover rather than measuring across it.

Very fast vehicles. A sixty-metre threshold at motorway speed triggers on almost every report, so compression collapses. That is correct behaviour — the addresses genuinely differ — but it is worth knowing that motorway-heavy fleets compress far less than urban delivery fleets, and budgeting accordingly.

Backfilling history. Running the filter over a historical archive is the cheapest way to size a reverse-geocoding budget before turning the pipeline on. The compression ratio from last month’s data predicts next month’s bill more accurately than any provider estimate.

One practical note on running the comparison: resolve the uncompressed sample from the cache where possible rather than from the provider, so the exercise itself does not become the most expensive thing you do that month.

Compression Ratio as a Health Signal

A stable compression ratio, and what a break in it means A line chart of the kept-pings ratio over eight weeks. The ratio holds steady around twenty-two percent, then drops sharply in the final week. An annotation notes that fleet size was unchanged, so the cause is a reporting-behaviour change and the reverse-geocoding bill will follow within a day. steady at ~22% kept ratio jumps — same fleet week 1 week 8 A firmware update, a new depot, or a failing GPS chip — all present as this line moving with no change in vehicles.

Integration Note

This filter runs before the cache lookup described in reverse geocoding workflows in Python, and the two compose multiplicatively: compression removes the pings whose answer cannot differ, and the cell cache removes the ones whose answer is already known. Running the cache first works but wastes lookups on pings that the filter would have discarded anyway.

The same sample is also the natural place to check that device identifiers are stable and that timestamps are monotonic, since both assumptions are load-bearing for this filter and neither is guaranteed by a tracker.