Rounding GPS Timestamps Without Breaking Trip Chaining

Rounding is order-preserving and interval-destroying: two events 90 seconds apart can land in the same 15-minute bin, and once they do, nothing in the released data says which came first. Trip chaining depends on that ordering, so a feed that rounds timestamps and drops the sequence has silently deleted every multi-leg journey it contains.

Core Calculation # permalink

Floor-rounding to a window $\Delta t$ maps event time $t$ to

This is monotone non-decreasing: $t_a < t_b \Rightarrow t'_a \le t'_b$. It never inverts an order, which is the good news. What it destroys is strictness — the moment two events share a bin, $t'_a = t'_b$ and the chain has a tie it cannot break.

The probability that two events separated by $g$ seconds collide in a window of $\Delta t$ is, for $g < \Delta t$,

which is the quantity that matters for chaining. A transfer with a 3-minute connection under a 15-minute window collides 80% of the time. A trip with a 30-minute activity between legs collides never.

Two mitigations exist, and they trade differently.

Preserve a leg index. Publish an ordinal leg_seq per trip alongside the rounded time. Order survives exactly; the cost is that the index is a quasi-identifier — a rider with seven legs in a day is distinctive — so it needs its own cap.

Preserve the gap, not the instant. Publish the rounded start time of the trip plus rounded durations between legs. Order survives, and the released quantities are relative rather than absolute, which is usually easier to defend. The cost is that a coarse duration accumulates: four legs at ±7.5 minutes each puts the last leg’s implied time up to half an hour off.

Worked numeric example # permalink

One rider, four legs, $\Delta t = 15$ min, bins anchored at the hour:

Legs 2 and 3 — the transfer — share a bin, which is exactly the pair a chaining algorithm most needs to order. Without a leg index the released trip reads as “two events at 08:15”, and the reconstruction has to guess whether the rider alighted then boarded or the reverse. Guessing wrong reverses the inferred direction of travel for the whole journey.

Python Implementation # permalink

from __future__ import annotations

import numpy as np
import pandas as pd


def cloak_preserving_chain(
    events: pd.DataFrame,
    window_s: int = 900,
    origin_s: int = 0,
    max_legs: int = 6,
    emit: str = "leg_index",
) -> pd.DataFrame:
    """Round event times while keeping multi-leg journeys reconstructable.

    Two orderings survive rounding: an explicit leg index, or rounded gaps
    measured from the trip's own start. Both are emitted from the same pass so a
    release can choose; publishing neither is what severs the chain.

    Args:
        events: columns `trip_id`, `t` (epoch seconds), sorted or not.
        window_s: generalization window; see the window-selection guide.
        origin_s: bin origin. Offset it from the timetable's own anchor so a bin
            edge does not coincide with scheduled departures.
        max_legs: contribution cap — a rider with more legs than this is
            distinctive, so the tail is truncated rather than published.
        emit: "leg_index" or "gaps".
    """
    if window_s <= 0:
        raise ValueError("window_s must be positive")

    df = events.sort_values(["trip_id", "t"]).copy()
    df["leg_index"] = df.groupby("trip_id").cumcount()
    df = df[df["leg_index"] < max_legs]                 # cap before anything else

    t = df["t"].to_numpy(dtype=np.int64)
    df["t_binned"] = ((t - origin_s) // window_s) * window_s + origin_s

    if emit == "gaps":
        first = df.groupby("trip_id")["t"].transform("min").to_numpy(dtype=np.int64)
        gap = t - first
        # Round the gap, not the instant: relative quantities are easier to
        # defend and do not leak the absolute clock a second time per leg.
        df["gap_binned_s"] = (gap // window_s) * window_s
        df["t_start_binned"] = ((first - origin_s) // window_s) * window_s + origin_s
        return df.drop(columns=["t", "t_binned", "leg_index"])

    return df.drop(columns=["t"])

Verification # permalink

The check is whether the released feed still supports chaining, and it has a clean pass/fail form.

def chain_reconstructable(released: pd.DataFrame, truth: pd.DataFrame) -> dict:
    """Fraction of trips whose leg order can be recovered from the release alone."""
    def order_key(g):
        cols = [c for c in ("t_binned", "leg_index", "gap_binned_s") if c in g]
        return g.sort_values(cols).index.tolist()

    ok = ties = 0
    for trip, g in released.groupby("trip_id"):
        rec = order_key(g)
        true_order = truth.loc[truth["trip_id"] == trip].sort_values("t").index.tolist()
        if "t_binned" in g and g["t_binned"].duplicated().any() and "leg_index" not in g:
            ties += 1                       # collided bin with nothing to break it
        ok += int(rec == true_order)
    n = released["trip_id"].nunique()
    return {
        "trips": n,
        "order_recovered": ok / max(n, 1),      # target 1.0
        "unbreakable_ties": ties / max(n, 1),   # target 0.0
    }

unbreakable_ties is the number to gate on. A release where 12% of trips contain a collided bin with no tiebreaker has lost 12% of its chaining, and that loss is invisible in any aggregate the feed publishes — the boarding counts are all still correct.

Run the collision-probability formula as a design check too, before generating anything: with the observed transfer-gap distribution and the candidate window, the expected collision rate is computable in a line, and it tells you whether a leg index is required or merely nice to have.

Edge Cases & Adjustments # permalink

• The leg index is a quasi-identifier. A trip with eight legs is distinctive on its own. Cap it — the implementation truncates at max_legs — and treat the cap as a published parameter, since a truncated trip is a different trip from the one the rider took.
• Bin edges aligned to the timetable. If bins start on the hour and departures do too, a record’s bin tells a reader which side of :00 it fell on. Offset origin_s, version the offset, and do not derive it from the data.
• Accumulating gap error. Under the gaps emission, each leg’s implied absolute time carries the rounding error of the trip start plus its own. Four legs at a 15-minute window puts the last leg up to half an hour from truth, which some analyses tolerate and route-level dwell estimation does not.
• Ties that are real. Two events genuinely simultaneous — a tap-out and a tap-in on an integrated fare gate — are not a rounding artefact and should not be broken. Distinguish them with an event-type field rather than an ordering.
• Interaction with jitter. Applying jitter after rounding can reintroduce order inversions, because the jitter is independent per record. Round last, or apply a single monotone transform, but never a rounding step followed by an independent perturbation of the same axis — the failure mode described under temporal cloaking and time obfuscation.

FAQ # permalink

Does publishing a leg index weaken the guarantee?

It adds a quasi-identifier, so yes, marginally — and it is usually the cheapest place to spend that. The alternative is either a feed with no chaining or a much narrower window, and the second is far more disclosive because it hands the timetable join back to the adversary.

Can I keep exact ordering by rounding to different bins per leg?

No. Any scheme that guarantees distinct bins for closely spaced events is guaranteeing a bound on the true gap, which is precisely the information rounding is supposed to remove. The ordering and the interval are separable; the ordering and a bound on the interval are not.

What about rounding to the nearest bin rather than flooring?

Nearest-rounding is also monotone and has the same collision behaviour, with one extra hazard: half the records move backwards in time, which can push an event before the trip start it is measured from. Floor is easier to reason about and easier to explain in a release note.

How does this interact with the spatial cell?

The k floor is evaluated on the joint space-time cell, so a wider window lets you keep a finer spatial cell at the same k. Sweep both axes together — the temporal axis usually buys more uniqueness reduction per unit of lost utility, as shown under estimating uniqueness of mobility traces.

Related # permalink

• Temporal Cloaking & Time Obfuscation — the window, the k condition and the jitter mechanics
• Choosing Temporal Cloaking Windows for Transit Feeds — sizing the window this guide then rounds to
• Trajectory Anonymization Techniques — sequence-level controls for whole paths
• Estimating Uniqueness of Mobility Traces — why the temporal axis moves uniqueness fastest

← Back to Temporal Cloaking & Time Obfuscation