w-Event Privacy for Streaming Trajectories

A vehicle emitting a location fix every second never stops producing data, so the finite privacy budget that protects a single snapshot is exhausted almost immediately if you spend a fixed $\varepsilon$ at every timestamp. w-event privacy solves the infinite-stream problem with one structural rule: guarantee $\varepsilon$-differential privacy over any sliding window of w consecutive timestamps rather than over the whole unbounded trace. This page is the budget-allocation deep-dive inside the parent guide on differential privacy for spatial trajectories, which lives under the Differential Privacy for Geospatial Data section. The concern here is narrow and mechanical: how a scheduler decides, at each incoming fix, how much of the window budget to spend versus reuse the previous release — the exact allocation logic that makes the sliding-window guarantee hold while keeping a parked-then-moving subject’s released trajectory usable. Everything below assumes the per-release noise is drawn by a calibrated spatial noise mechanism and that the cumulative spend is reconciled against the accounting discipline in privacy budget management.

Parameter Configuration and Calibration

The single invariant every w-event scheme must preserve is that the sum of $\varepsilon$ spent across any w consecutive timestamps is at most $\varepsilon_{\text{total}}$. Formally, for a spend sequence $\varepsilon_1, \varepsilon_2, \dots$ over the stream, the mechanism satisfies w-event $\varepsilon_{\text{total}}$-privacy iff $\sum_{k=t-w+1}^{t} \varepsilon_k \le \varepsilon_{\text{total}}$ for every $t$. Because that constraint slides, spending heavily now silently constrains what you can spend for the next $w-1$ steps — which is exactly why naive per-step allocation collapses. The knobs below decide how that fixed window budget is spread over a bursty movement pattern.

The strategy choice is the substance. Uniform allocation is trivially safe — w steps each spending $\varepsilon_{\text{total}}/w$ sum to exactly $\varepsilon_{\text{total}}$ — but wasteful: a parked vehicle burns the same budget standing still as it does cornering, so every release is drowned in noise scaled to a tiny $\varepsilon_{\text{total}}/w$. Adaptive schemes exploit the fact that trajectories are mostly stationary. When the new fix barely differs from the last release, publishing a fresh noisy value is strictly worse than reusing the previous one — the noise you would add exceeds the real change. So the mechanism approximates (re-emits the last release, spends nothing) and banks the budget for the moment the subject actually moves. Budget Distribution dissipates the residual geometrically ($\varepsilon_{\text{pub}} = \varepsilon_{\text{rm}}/2$) so it never fully commits; Budget Absorption keeps a uniform per-step allotment but lets a burst of movement absorb the budget that quiet neighbours left on the table, then nullifies future steps to keep the window sum capped.

The publish-versus-approximate decision is a direct comparison: publish only when dissimilarity > sensitivity / epsilon_pub. The right side is the expected error of a fresh release; the left is the real change. Releasing beats reusing precisely when the subject moved more than the noise would blur.

Reference Implementation

WEventBudgetAllocator is a single self-contained scheduler. It keeps a rolling record of the $\varepsilon$ spent at the most recent $w-1$ timestamps, computes the residual budget the current step may spend without breaching any window that contains it, and applies the publish-versus-reuse test. It performs no noise sampling itself — sensitivity and the returned noise_scale are the contract with the downstream Laplace stage — so the class is the pure allocation policy, easy to test in isolation.

from __future__ import annotations

from collections import deque
from dataclasses import dataclass
from typing import Deque, List, Literal

Strategy = Literal["uniform", "distribution"]


@dataclass(frozen=True)
class Release:
    """Outcome of one timestamp's budget request."""
    timestamp: int
    published: bool        # True = fresh noisy release; False = reuse previous
    epsilon_spent: float   # 0.0 on a reuse step
    noise_scale: float     # Laplace b = sensitivity / epsilon_spent (inf on reuse)


class WEventBudgetAllocator:
    """Allocate an epsilon budget across an infinite location stream so the
    total epsilon spent in ANY sliding window of w consecutive timestamps
    never exceeds epsilon_total -- the defining invariant of w-event privacy.

    A rolling deque holds the epsilon spent at the most recent w-1 committed
    timestamps. At each new timestamp the residual budget is epsilon_total
    minus that rolling sum, so committing a publication can never push any
    window over the cap. Skipping a publication (reuse) spends zero and lets
    the residual recover as old spends age out of the window -- this is what
    buys budget for the moments a subject actually moves.
    """

    def __init__(
        self,
        epsilon_total: float,
        w: int,
        sensitivity: float = 1.0,
        strategy: Strategy = "distribution",
    ) -> None:
        if epsilon_total <= 0:
            raise ValueError("epsilon_total must be positive")
        if w < 1:
            raise ValueError("w (window width) must be >= 1")
        self.epsilon_total: float = epsilon_total
        self.w: int = w
        self.sensitivity: float = sensitivity
        self.strategy: Strategy = strategy
        # spends of the most recent (w-1) committed timestamps
        self._window: Deque[float] = deque(maxlen=max(w - 1, 1))
        self._t: int = 0

    def _residual(self) -> float:
        """Budget still spendable now without breaching the cap on any window
        that includes the current timestamp."""
        # For w == 1 the window is empty and every step gets the full budget.
        spent = sum(self._window) if self.w > 1 else 0.0
        return self.epsilon_total - spent

    def request(self, dissimilarity: float) -> Release:
        """Decide publish-vs-reuse for the current timestamp.

        `dissimilarity` is the already-computed distance between the fresh
        statistic and the last released one -- e.g. mean displacement of the
        trajectory point in metres. We publish only when a fresh release would
        be MORE accurate than reusing the stale one: when the real movement
        exceeds the noise we would have to add under the residual budget.
        Otherwise we reuse and spend nothing, banking budget for later motion.
        """
        self._t += 1
        residual = self._residual()

        # Hard floor: no budget left in this window -> must reuse.
        if residual <= 1e-12:
            return self._commit(published=False, epsilon=0.0)

        # Candidate publication budget under the chosen strategy.
        if self.strategy == "uniform":
            eps_pub = min(self.epsilon_total / self.w, residual)
        else:  # Budget Distribution: spend half the residual, reserve the rest
            eps_pub = residual / 2.0

        # Expected error of a fresh release == Laplace scale b = sensitivity / eps.
        noise_scale = self.sensitivity / eps_pub
        # Publish only if the subject moved more than the noise would blur;
        # a reuse leaks nothing new, so approximating stale data is "free".
        if dissimilarity > noise_scale:
            return self._commit(True, eps_pub, noise_scale)
        return self._commit(published=False, epsilon=0.0)

    def _commit(self, published: bool, epsilon: float,
                noise_scale: float = float("inf")) -> Release:
        """Record the spend in the rolling window and advance the clock."""
        if self.w > 1:
            self._window.append(epsilon)
        return Release(self._t, published, epsilon, noise_scale)

Each publish under distribution spends at most half the residual, so a fresh window sum can only ever move from $s$ to $s + (\varepsilon_{\text{total}} - s)/2$, which stays strictly below $\varepsilon_{\text{total}}$; uniform caps each spend at $\varepsilon_{\text{total}}/w$. In both cases the cap holds by construction — but “by construction” is exactly the kind of claim that rots when someone edits the residual math, so it must be pinned by an executable test.

Validation Checkpoint

The harness below simulates a subject that alternates long stationary dwells with bursts of movement, runs the allocator over the stream, and then brute-forces the invariant: for every contiguous window of width w, the summed spend must not exceed $\varepsilon_{\text{total}}$. A misconfigured residual would let a window quietly overspend and void the privacy claim without raising, so this check belongs in CI.

import numpy as np


def _validate() -> None:
    rng = np.random.default_rng(42)
    w, eps_total = 20, 1.0
    alloc = WEventBudgetAllocator(eps_total, w=w, sensitivity=50.0,
                                  strategy="distribution")

    # 500 fixes: alternating "parked" phases (dissimilarity ~ 0) and
    # "driving" phases (large displacement) -- the realistic bursty pattern.
    releases: List[Release] = []
    for t in range(500):
        driving = (t // 25) % 2 == 1
        dis = float(rng.uniform(200, 400)) if driving else float(rng.uniform(0, 5))
        releases.append(alloc.request(dis))
    spends = [r.epsilon_spent for r in releases]

    # 1. THE invariant: every sliding window of width w spends <= eps_total.
    for start in range(len(spends) - w + 1):
        window_sum = sum(spends[start:start + w])
        assert window_sum <= eps_total + 1e-9, (
            f"window [{start}, {start + w}) spent {window_sum} > {eps_total}"
        )

    # 2. Semantics: published steps cost >0; reuse steps cost exactly 0.
    assert all(r.epsilon_spent > 0.0 for r in releases if r.published)
    assert all(r.epsilon_spent == 0.0 for r in releases if not r.published)

    # 3. Adaptivity: the scheme publishes during motion, holds during dwell.
    assert any(r.published for r in releases), "allocator never published"
    assert any(not r.published for r in releases), "allocator never reused"

    # 4. Uniform strategy respects the cap under a worst case of constant motion.
    uni = WEventBudgetAllocator(eps_total, w=w, sensitivity=50.0,
                                strategy="uniform")
    uni_spends = [uni.request(1e9).epsilon_spent for _ in range(200)]
    for start in range(len(uni_spends) - w + 1):
        assert sum(uni_spends[start:start + w]) <= eps_total + 1e-9

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


if __name__ == "__main__":
    _validate()

The brute-force sweep is deliberately not clever: it re-derives the window sums from the raw spend log rather than trusting the allocator’s internal accounting, so a bug in _residual cannot hide behind the same bug in the check. Pair this with the exhaustion detection in privacy budget management to alert before a window pins to zero residual and silently degrades to constant reuse.

Incident Response and Edge Cases

• Adversarial dissimilarity oscillation. An attacker who can nudge the raw signal so dissimilarity sits just above noise_scale on alternating steps forces maximal publication and drives every window to the cap, collapsing utility to pure noise. Detection: monitor the publish rate per window; a sustained rate near $w/2$ under distribution is anomalous for real mobility. Remediation: compute the dissimilarity itself under a small reserved sub-budget (so the decision is private too), or add hysteresis — require dissimilarity to exceed noise_scale by a margin before publishing.
• Window pinned to zero residual. After a movement burst spends most of the budget, the next $w-1$ steps may have near-zero residual and be forced to reuse even if the subject keeps moving, producing a stale, laggy released trajectory. Detection: residual stays below a floor across a full window. Remediation: raise epsilon_total, shorten w, or switch to Budget Absorption so quiet steps pre-fund the burst instead of the burst starving its successors.
• Reuse of a coordinate that is itself sensitive. Reuse spends no new budget, but it re-publishes a value already released — fine for privacy, yet if the first release under-noised the point, every reuse propagates that error. Detection: audit that the initial noise_scale of each published segment matches $\Delta f / \varepsilon_{\text{pub}}$. Remediation: never let a downstream stage re-noise a reused value (it would spend budget for no new information); fix calibration at the publish step via the spatial noise mechanisms layer.
• Restart amnesia across process boundaries. If the allocator restarts and forgets its rolling window, the first w-1 steps after restart treat the full budget as free and can overspend a window that straddles the restart. Detection: reconcile spend logs across the restart boundary. Remediation: persist the deque of recent spends (or the timestamped spend log) durably and rehydrate it before serving the first post-restart fix.

Frequently Asked Questions

Related

• Differential Privacy for Spatial Trajectories — the parent guide on trajectory-level DP that this budget-allocation deep-dive sits inside.
• Differential Privacy for Geospatial Data — the section covering noise mechanisms, aggregation, and geo-indistinguishability.
• Spatial Noise Mechanisms — the Laplace and Gaussian stage that consumes the noise_scale this allocator returns.
• Privacy Budget Management — cross-window accounting, exhaustion detection, and durable spend logs.
• Geo-Indistinguishability for Location Privacy — the per-release metric-privacy alternative when you protect single points rather than windows.

Up: Differential Privacy for Spatial Trajectories · Differential Privacy for Geospatial Data