Differential Privacy for Spatial Trajectories

A mobility team runs a live per-minute feed: connected vehicles report their position, a stream processor bins each vehicle onto a road-network cell, and the platform publishes a rolling count of how many vehicles occupy each segment — forever, one release every minute. The moment you try to make that feed differentially private, the snapshot mechanisms that work for a one-shot heatmap fall apart, because a trajectory is not a bag of independent points. Consecutive positions are tightly correlated by physics and the road graph, so noise added independently to each point can be filtered back out, and every release you make about the same subject composes against a single, shared privacy budget. Trajectories are the hardest target in differential privacy for exactly this reason: the individual point is not the secret — the whole path is the secret, and the stream never ends. This guide is about choosing the right unit of protection (event, w-event, or user), allocating a finite $\varepsilon$ across a sliding window of an unbounded stream, and calibrating the sensitivity of the trajectory statistics you actually release.

This page sits inside the differential privacy for geospatial data section, downstream of the point-level tools it composes: the spatial noise mechanisms that calibrate a single release, and the differentially private spatial aggregation that turns a batch of points into a protected histogram. Trajectory privacy is what you reach for when those releases repeat over time for the same moving subjects. The streaming accountant here allocates budget uniformly across a window; the adaptive budget-distribution and budget-absorption allocators that spend more where the data actually changes are the subject of the child guide on w-event privacy for streaming trajectories. Budget accounting across all of these releases is the concern of privacy budget management, and the reconstruction attack this whole page defends against is catalogued under threat mapping for GIS data.

Prerequisites & Streaming Budget Setup

Everything below assumes canonical EPSG:4326 input already binned to a spatial index — a road-network segment id, a grid cell, or an origin–destination (OD) pair — so the object you release at each timestamp is a fixed-length integer count vector, not raw coordinates. The reference code needs only numpy for the Laplace draws and the Python standard library (collections.deque, dataclasses) for the sliding-window accountant; nothing here requires a heavyweight DP framework, and keeping the accountant transparent is deliberate because the window invariant is the whole security argument.

Three things must be settled before the first release:

• A declared budget horizon. Pick the total budget $\varepsilon$ that any window of $w$ timestamps is allowed to spend, and tie it to a concrete control from privacy budget management rather than a folklore value. A common streaming default is $\varepsilon = 1.0$ over a window, with $w$ chosen from how long a subject stays identifiable in the feed.
• A per-timestamp sensitivity. The count vector you publish has an $L_1$ sensitivity $\Delta f$ equal to the largest change one user can cause in a single release. When each user occupies exactly one cell at a time, $\Delta f = 1$. If a user can register in several cells at once (multi-modal segments, overlapping OD pairs), $\Delta f$ rises and the noise scales with it.
• A defined event, and thus a definition of the secret. “One event” might be one timestamp of one user, or the user’s entire presence in the feed. That choice is the granularity decision of Step 1, and it is the single most consequential parameter on the page — get it wrong and the accountant is rigorous about protecting the wrong thing.

Step 1: Pick the Privacy Granularity for the Release

Differential privacy always protects a neighbouring-dataset relation, and for streams there are three standard choices for what “neighbouring” means. Event-level privacy makes two streams neighbours if they differ in a single event at a single timestamp: it hides whether one user was at one place at one instant, and nothing more. User-level privacy makes two streams neighbours if they differ in all events of one user across the entire, possibly infinite, stream: it hides the user’s whole trajectory. w-event privacy is the interpolation introduced by Kellaris and colleagues: two streams are neighbours if they differ in any window of $w$ consecutive timestamps, so it hides any length-$w$ sub-trajectory of any user.

The reason w-event exists is that the two extremes are both unusable on a live feed. Event-level protection is too weak because a trajectory is a correlated sequence — hiding one point while releasing its neighbours leaks the point through motion continuity and the road graph. User-level protection is too strong to be useful on an unbounded stream: the whole path is the secret, the stream never ends, and splitting one finite $\varepsilon$ across infinitely many timestamps drives the per-release budget to zero and the noise to infinity. w-event fixes both by bounding the temporal reach of the guarantee to a window you can afford to protect.

from __future__ import annotations

from dataclasses import dataclass
from typing import Literal

Granularity = Literal["event", "w-event", "user"]


@dataclass(frozen=True)
class ReleasePlan:
    """The unit of protection selected for a streaming trajectory release."""
    granularity: Granularity
    w: int              # window width in timestamps (1 == event, horizon == user)
    sensitivity: float  # L1 sensitivity of the per-timestamp count vector


def choose_granularity(release_kind: str, horizon: int, window: int = 1) -> ReleasePlan:
    """Map release semantics onto a (granularity, w, sensitivity) plan.

    A one-shot snapshot protects a single timestamp (event-level); a bounded
    live feed protects any w-length sub-trajectory (w-event); a whole-history
    export protects the entire path (user-level, modelled as w = horizon).
    """
    if release_kind == "snapshot":
        return ReleasePlan("event", 1, 1.0)          # w == 1 is exactly event-level
    if release_kind == "stream":
        if window < 1:
            raise ValueError("streaming release needs a window w >= 1")
        return ReleasePlan("w-event", window, 1.0)   # the middle ground
    if release_kind == "full-history":
        if horizon < 1:
            raise ValueError("user-level needs a finite horizon to allocate over")
        return ReleasePlan("user", horizon, 1.0)     # w spans the subject's lifetime
    raise ValueError(f"unknown release kind: {release_kind!r}")

Notice that all three granularities are the same accountant with a different $w$: event-level is $w = 1$, user-level is $w$ equal to the number of timestamps in the subject’s lifetime, and w-event is anything in between. That is why the rest of this guide implements one sliding-window mechanism rather than three special cases.

Step 2: Define the Sliding Window and Per-Window Budget

The w-event guarantee is a promise about every window, not just the current one: for any run of $w$ consecutive timestamps, the sum of the privacy budgets spent inside it must not exceed $\varepsilon$. Concretely, if $\varepsilon_i$ is the budget spent at timestamp $i$, the invariant is

$$\sum_{i=t-w+1}^{t} \varepsilon_i \;\le\; \varepsilon \qquad \text{for every } t.$$

Because every window ends at some timestamp, it suffices to enforce the constraint at the moment of each release: before choosing $\varepsilon_t$, look back at the budget already committed in the preceding $w-1$ timestamps and cap $\varepsilon_t$ at whatever remains. Maintaining exactly the last $w-1$ debits in a bounded queue turns the window invariant into an $O(1)$ check per release.

from collections import deque
from dataclasses import dataclass, field
from typing import Deque
import numpy as np


class BudgetSaturatedError(RuntimeError):
    """Raised when a window has no budget left to spend at this timestamp."""


@dataclass
class TrajectoryDPStream:
    """w-event differentially private release over an unbounded trajectory stream.

    Guarantees that the epsilon spent across *any* window of `w` consecutive
    timestamps never exceeds `epsilon_total`, which protects the presence of any
    user's sub-trajectory of length <= w. Event-level (w == 1) and user-level
    (w == horizon) are the limiting cases of this one accountant.
    """
    epsilon_total: float
    w: int
    sensitivity: float = 1.0
    adaptive: bool = False
    _spent: Deque[float] = field(default_factory=deque, init=False)   # last w-1 debits
    _rng: np.random.Generator = field(default_factory=np.random.default_rng, init=False)
    last_epsilon: float = field(default=0.0, init=False)

    def __post_init__(self) -> None:
        if self.epsilon_total <= 0:
            raise ValueError("epsilon_total must be positive")
        if self.w < 1:
            raise ValueError("window w must be >= 1")
        if self.sensitivity <= 0:
            raise ValueError("sensitivity must be positive")

    def _available(self) -> float:
        """Budget still spendable now without breaching the co-window invariant."""
        return self.epsilon_total - sum(self._spent)

The queue holds only the $w-1$ debits that share a window with the timestamp about to be released, so _available is precisely the headroom the invariant leaves. A TrajectoryDPStream(epsilon_total=1.0, w=1) degenerates to event-level: the queue is always empty and every release gets the full budget. A stream constructed with w equal to the subject horizon is user-level.

Step 3: Allocate the Budget Across Timestamps (Uniform vs Adaptive)

With the window headroom in hand, the allocator decides how much of it to spend now. The safe, boring default is uniform allocation: give each timestamp $\varepsilon_t = \varepsilon / w$, so any $w$ consecutive releases sum to exactly $\varepsilon$. Uniform allocation is a good baseline because its behaviour is completely predictable and its noise is stationary, but it pays a real price — the Laplace scale becomes $b = \Delta f \cdot w / \varepsilon$, so widening the window to protect a longer sub-path multiplies the noise linearly. That is the fundamental w-event trade-off: stronger temporal protection costs proportionally more noise on every release.

The alternative is adaptive allocation, which spends more budget on timestamps where the underlying counts actually moved and near-zero where the map is static, then reuses the previous release for free (post-processing) when nothing changed. Doing that well — deciding how much to dissipate versus absorb, and doing it without leaking the change points themselves — is the entire subject of the child guide on w-event privacy for streaming trajectories. Here the adaptive branch is deliberately a placeholder that spends half of the remaining headroom, enough to show the mechanics and the invariant without the production allocator.

    def _allocate(self) -> float:
        """Choose epsilon_t for this timestamp, always capped at the window headroom."""
        available = self._available()
        if available <= 1e-12:
            return 0.0
        if self.adaptive:
            # Placeholder: spend half of what remains. The real budget-distribution
            # / budget-absorption allocator that adapts to data change lives in the
            # child guide; do NOT ship this branch as your production scheme.
            candidate = available / 2.0
        else:
            candidate = self.epsilon_total / self.w   # uniform: w-window sums to epsilon
        # Capping at `available` is what makes the co-window invariant hold for ANY
        # allocator, uniform or adaptive — no window can ever exceed epsilon_total.
        return min(candidate, available)

The load-bearing line is the final min(candidate, available). It means the invariant is guaranteed by the accountant, not by the allocator: any strategy that respects the headroom cap is w-event private, so the child guide can swap in a far cleverer allocation without ever being able to violate the budget.

Step 4: Apply the Per-Timestamp Mechanism

A release does four things in order: slide the window, allocate $\varepsilon_t$, add Laplace noise scaled to $b = \Delta f / \varepsilon_t$, and debit the budget. Sliding first is what keeps the queue holding exactly the co-window debits; debiting last is what makes the next release see this one’s spend.

    def release(self, counts: np.ndarray) -> np.ndarray:
        """Release one timestamp's spatial count vector under the window budget.

        `counts` is the per-cell vector for this timestamp — vehicle counts over
        road-network segments, or the flattened cells of an OD matrix.
        """
        # 1. Slide: retain only the w-1 debits that co-occupy this release's window.
        while len(self._spent) > self.w - 1:
            self._spent.popleft()
        # 2. Allocate under the headroom cap; a saturated window must not overspend.
        eps_t = self._allocate()
        if eps_t <= 0.0:
            raise BudgetSaturatedError(
                "w-event budget exhausted for this window; re-publish the prior "
                "release (free post-processing) or widen the release interval"
            )
        # 3. Per-timestamp Laplace mechanism. Scale grows with the window: at uniform
        #    allocation b = sensitivity * w / epsilon_total, the cost of protecting w.
        scale = self.sensitivity / eps_t
        noisy = counts.astype(float) + self._rng.laplace(0.0, scale, size=counts.shape)
        # 4. Debit the window and record the spend for accounting / audit.
        self._spent.append(eps_t)
        self.last_epsilon = eps_t
        # Non-negativity is post-processing on a DP release: it consumes no budget.
        return np.maximum(noisy, 0.0)

Two design choices matter for privacy. First, noise is added to the aggregate count vector, never to individual coordinates — the mechanism protects the histogram, and the fact that a specific user is in the stream is hidden by the noise on the cell they occupy. Second, the np.maximum(..., 0.0) clamp is applied after the noisy release and therefore spends nothing, because any deterministic function of a differentially private output is still differentially private.

Step 5: Aggregate and Release the Protected Statistic

The vector fed to release comes from an aggregation step whose sensitivity you must control, because the accountant’s sensitivity argument is a claim about it. The safe pattern is to bin every active user onto exactly one cell per timestamp so that adding or removing a user changes exactly one entry by one — an $L_1$ sensitivity of 1. OD matrices are the same idea: each user contributes one origin–destination pair, so one flattened cell moves by one. Where a user can legitimately land in several cells at once, either raise sensitivity to that maximum or clip each user’s contribution so the claim stays true.

def road_network_count_vector(active_users: dict[int, int], n_cells: int) -> np.ndarray:
    """Bin users onto road-network cells for one timestamp.

    `active_users` maps user_id -> cell_index, and each user is in exactly one
    cell, so adding or removing one user changes exactly one cell by one: the
    L1 sensitivity is 1, which is precisely what the accountant assumes.
    """
    counts = np.zeros(n_cells, dtype=float)
    for cell in active_users.values():
        if not 0 <= cell < n_cells:
            raise ValueError(f"cell index {cell} out of range [0, {n_cells})")
        counts[cell] += 1.0
    return counts


def od_matrix_vector(pairs: list[tuple[int, int]], n_zones: int) -> np.ndarray:
    """Flatten origin->destination trips into a per-cell count vector.

    One user contributes one (origin, destination) pair, so the flattened
    matrix also has L1 sensitivity 1 per timestamp.
    """
    m = np.zeros((n_zones, n_zones), dtype=float)
    for origin, dest in pairs:
        m[origin, dest] += 1.0
    return m.reshape(-1)   # release the flattened matrix as a single count vector

Once you hold the count vector, the loop is simply: build the vector, call stream.release, optionally round the noisy result to integers for a count-typed dashboard (rounding is post-processing, still free), and publish. When the accountant raises BudgetSaturatedError, the correct response is to re-publish the previous release — which leaks nothing new — rather than to spend budget the window does not have.

Step 6: Validate the Window-Level Guarantee

The whole security argument is the co-window invariant, so it must be asserted mechanically over a simulated stream rather than reasoned about by eye. The helper below is the one check every deployment should run in CI: slide a width-$w$ window across the recorded debits and confirm no window ever exceeds $\varepsilon$.

from typing import List


def assert_window_guarantee(debits: List[float], w: int, epsilon: float) -> None:
    """Fail loudly if any window of w consecutive releases overspends epsilon."""
    for i in range(len(debits) - w + 1):
        spend = sum(debits[i:i + w])
        assert spend <= epsilon + 1e-9, f"window @{i} overspent: {spend:.4f} > {epsilon}"

Run this over a few thousand simulated timestamps under both the uniform and adaptive allocators and against the two limiting granularities. If it passes for every window, the release is w-event private by construction regardless of how the budget was allocated inside each window.

Threat Model Considerations

Trajectory releases invite attacks that snapshot releases never see, because the adversary can exploit time:

• Temporal-correlation filtering. An adversary who models motion — a Kalman filter over the road graph, or a learned mobility prior — can average independent per-point noise across correlated consecutive positions and recover a path far more accurately than the per-point $\varepsilon$ suggests. This is why event-level protection on a correlated stream is a trap; w-event budgets the window, so the correlated neighbours an attacker would exploit are inside the protected set.
• Trajectory reconstruction. Even from noisy counts, map-matching and continuity constraints can stitch a plausible path back together — the dominant vector catalogued under threat mapping for GIS data. Widening $w$ raises the noise the reconstruction must fight through.
• Composition across releases. Every minute you publish about the same subjects spends budget. Without a window cap, an adversary differences overlapping releases to peel the noise back; the sliding-window accountant is exactly the defence, and it must be coordinated with system-wide privacy budget management.
• Sensitivity understatement. If a user can occupy several cells per timestamp but the accountant is told sensitivity=1, the true guarantee is weaker than the claimed one. Clip contributions or raise $\Delta f$ so the claim is honest.
• Sparse-region singling-out. In a cell with one occupant, even correct noise may leave the count identifiable across a window. Enforce a population floor by suppressing or coarsening low-count cells before release, consistent with the aggregation controls in differentially private spatial aggregation.

Validation & Compliance Checklist

Wire each control to a measurable pass criterion rather than a review comment:

1. Co-window invariant — PASS if assert_window_guarantee holds for every window across a $\ge 10^4$-timestamp simulation, under both uniform and adaptive allocation. This is the core guarantee; fail the build on any breach.
2. Granularity limits — PASS if a w == 1 stream spends the full $\varepsilon$ per release (event-level) and a w == horizon stream never lets the whole-history spend exceed $\varepsilon$ (user-level).
3. Sensitivity honesty — PASS if the aggregation step provably changes by at most sensitivity entries of magnitude one when any single user is added or removed, verified on a differencing test.
4. Noise calibration — PASS if the empirical Laplace scale of released minus true counts matches $\Delta f / \varepsilon_t$ within sampling tolerance, so no release is under-noised.
5. Saturation behaviour — PASS if an exhausted window raises BudgetSaturatedError and the caller re-publishes the prior release rather than emitting an unbudgeted one.
6. Compliance binding — PASS if the window $\varepsilon$ and $w$ resolve to a documented control (a retention window, a per-subject budget ceiling) under privacy budget management.

The harness below exercises criteria 1, 2, and 5 directly and is safe to run in CI:

import math


def _validate() -> None:
    rng = np.random.default_rng(7)
    eps, w, n_cells = 1.0, 5, 8

    # --- w-event stream: every window of w must spend <= epsilon ---
    stream = TrajectoryDPStream(epsilon_total=eps, w=w, sensitivity=1.0)
    debits: List[float] = []
    for _ in range(400):
        users = {uid: int(rng.integers(n_cells)) for uid in range(rng.integers(5, 40))}
        counts = road_network_count_vector(users, n_cells)
        noisy = stream.release(counts)
        assert noisy.shape == counts.shape
        assert (noisy >= 0).all(), "counts must stay non-negative after post-processing"
        debits.append(stream.last_epsilon)
    assert_window_guarantee(debits, w, eps)                     # criterion 1

    # --- event-level limiting case: w == 1 spends the full budget each release ---
    ev = TrajectoryDPStream(epsilon_total=eps, w=1)
    ev.release(np.zeros(4))
    assert math.isclose(ev.last_epsilon, eps), "event-level must spend full epsilon"  # crit. 2

    # --- user-level limiting case: whole-history spend stays under epsilon ---
    horizon = 20
    user = TrajectoryDPStream(epsilon_total=eps, w=horizon)
    user_debits: List[float] = []
    for _ in range(horizon):
        user.release(np.zeros(4))
        user_debits.append(user.last_epsilon)
    assert sum(user_debits) <= eps + 1e-9, "user-level window overspent"              # crit. 2

    # --- saturation: a window already fully committed must refuse to overspend ---
    # A front-loading (budget-absorption) allocator can commit all of epsilon early
    # in a window, leaving a later timestamp with zero headroom. Pin that state and
    # confirm the accountant raises rather than emitting an unbudgeted release.
    pinned = TrajectoryDPStream(epsilon_total=eps, w=3)
    pinned._spent.extend([eps / 2, eps / 2])   # two prior debits sum to epsilon
    saturated = False
    try:
        pinned.release(np.zeros(4))
    except BudgetSaturatedError:
        saturated = True
    assert saturated, "a fully-committed window must refuse a further spend"           # crit. 5

    print("all w-event trajectory invariants hold")


if __name__ == "__main__":
    _validate()

Failure Modes & Remediation

w-event releases fail quietly — a wrong window, an understated sensitivity, or a stalled feed all produce plausible-looking output that no longer carries the claimed guarantee.

• Window too narrow for the correlation length. If subjects stay identifiable for longer than $w$ timestamps, an adversary attacks across window boundaries where the budget resets. Detection: measure how many consecutive timestamps a typical subject remains linkable. Remediation: raise $w$ to cover that correlation length, accepting the proportional noise increase, or coarsen the release cadence.
• Sensitivity understated. A user lands in several cells per timestamp but the accountant assumes one, so the real $\varepsilon$ is a multiple of the claimed one. Detection: the differencing test in checklist item 3 fails. Remediation: clip each user to one cell, or set sensitivity to the true per-timestamp maximum.
• Silent saturation. Under an aggressive adaptive allocator a window drains and the stream either stalls or, worse, an operator “fixes” it by spending anyway. Detection: BudgetSaturatedError frequency spikes. Remediation: re-publish the previous release on saturation (free), and move to the disciplined budget-absorption allocator in the w-event child guide.
• Cross-stream budget leakage. The same subjects appear in a second feed (an OD matrix and a segment-count feed), and each accountant is unaware of the other, so their combined spend exceeds $\varepsilon$. Detection: audit which releases touch a shared population. Remediation: share one budget ledger across correlated feeds via privacy budget management.
• Clock skew and gap handling. Missing or out-of-order timestamps mis-align the window, so the queue no longer holds the true co-window debits. Detection: assert monotonic timestamps at ingestion. Remediation: treat a gap as spent-nothing timestamps that still advance the window, and reject reordered events at the boundary.

Frequently Asked Questions

Related

This guide is part of the Differential Privacy for Geospatial Data section — start there for how point noise, aggregation, geo-indistinguishability, and trajectory privacy fit into one release pipeline.

• w-Event Privacy for Streaming Trajectories — the deep dive on adaptive budget-distribution and budget-absorption allocators this page defers.
• Spatial Noise Mechanisms — how the per-timestamp Laplace and Gaussian releases are calibrated.
• Differentially Private Spatial Aggregation — building the count vectors and enforcing population floors before release.
• Privacy Budget Management — sharing one budget ledger across correlated feeds and subjects.
• Threat Mapping for GIS Data — trajectory reconstruction and the temporal-correlation attacks this page defends against.

Up: Differential Privacy for Geospatial Data