Composing Privacy Budgets Across Spatial Queries

When a pipeline answers several spatial queries against the same population, the total privacy loss composes: sequential queries on overlapping data add their ε values, disjoint partitions take the maximum, and multi-query accounting under zero-concentrated DP keeps the cumulative bound tight enough to stay within a fixed budget cap.

Core Calculation # permalink

Composition is the accounting layer on top of any noise mechanism. Whether each release uses the Laplace mechanism from applying Laplace noise to latitude/longitude pairs or a Gaussian one, the question is the same: what is the combined ε a single individual is exposed to across all releases?

Sequential composition # permalink

If k mechanisms each satisfy εᵢ-differential privacy and all read data that a given individual may contribute to, the combined release satisfies:

This is the safe default whenever query extents overlap.

Parallel composition # permalink

If the mechanisms operate on disjoint subsets of records — for example counts over non-overlapping grid cells — each individual is touched by exactly one query, so the loss is the worst single query:

Advanced composition # permalink

For k releases each at (ε₀, δ₀), the advanced composition bound gives a sub-linear ε at the cost of a small added δ. For any δ' > 0:

zCDP / Renyi accounting # permalink

Zero-concentrated DP (zCDP) tracks a single parameter ρ that is simply additive:

A pure εᵢ-DP mechanism is (εᵢ²/2)-zCDP, and the Gaussian mechanism with sensitivity Δf and scale σ gives ρ = Δf²/(2σ²). Convert accumulated ρ back to an (ε, δ) guarantee with:

Because ρ adds linearly but the ε conversion carries a square-root term, the cumulative ε for many small queries grows roughly like √k rather than k.

Worked example: three H3 resolution tiers plus a daily refresh # permalink

Publish a mobility density map at three H3 hexagon resolutions from one dataset. Within a single resolution the hexagons are disjoint, so the cells compose in parallel — the tier costs one ε, not one per cell. Across resolutions, each individual appears in all three tiers, so the tiers compose sequentially:

Now suppose that map refreshes daily against a rolling window that re-reads each user. Every refresh is a fresh sequential release, so over a 30-day horizon under basic accounting:

That blows any reasonable cap. Switching to zCDP: each daily map is (ε=1.0)-DP → ρ = 1.0²/2 = 0.5. Thirty refreshes give ρ_total = 15.0, and converting at δ = 10⁻⁶:

The zCDP number is worse here because per-query ε=1.0 is large — zCDP wins for many small queries, not few large ones. The real fix is bounding the horizon and caching, covered in the edge cases below.

Python Implementation # permalink

The accountant below tracks spent ε across queries, distinguishing disjoint (parallel) partitions from overlapping (sequential) extents, and exposes a zCDP path for many-query workloads. No spatial CRS is involved at the accounting layer — the counts it protects come from queries already binned in a stated CRS such as WGS84 (EPSG:4326).

from __future__ import annotations
import math
from dataclasses import dataclass, field


@dataclass
class SpatialQuery:
    """A single differentially private spatial release.

    Attributes:
        name: Human-readable identifier, e.g. "density_r8".
        epsilon: Pure-DP budget spent by this query (> 0).
        partition_group: Queries sharing a group_key touch DISJOINT record
            subsets (e.g. non-overlapping H3 cells) and compose in parallel.
            None means the query overlaps everything -> sequential.
    """
    name: str
    epsilon: float
    partition_group: str | None = None


@dataclass
class PrivacyBudgetAccountant:
    """Tracks cumulative epsilon across spatial queries under a fixed cap.

    Parallel composition (disjoint partitions) contributes max(epsilon) per
    group; sequential composition (overlapping extents) sums epsilon. A single
    person can appear in at most one partition of a group, which is what makes
    the parallel bound sound -- callers MUST guarantee that disjointness.
    """
    budget_cap: float
    delta: float = 1e-6
    _queries: list[SpatialQuery] = field(default_factory=list)

    def spend(self, query: SpatialQuery) -> None:
        """Record a query and refuse it if it would breach the cap."""
        if query.epsilon <= 0:
            raise ValueError(f"epsilon must be > 0, got {query.epsilon!r}")
        projected = self.total_epsilon_basic(extra=query)
        if projected > self.budget_cap + 1e-12:
            raise ValueError(
                f"Query {query.name!r} would push cumulative epsilon to "
                f"{projected:.4f}, over cap {self.budget_cap:.4f}"
            )
        self._queries.append(query)

    def total_epsilon_basic(self, extra: SpatialQuery | None = None) -> float:
        """Basic composition: sum across groups, max within a disjoint group."""
        queries = self._queries + ([extra] if extra else [])
        # Sequential (no partition_group) queries always add.
        total = sum(q.epsilon for q in queries if q.partition_group is None)
        # Each disjoint group contributes only its worst-case single query.
        groups: dict[str, float] = {}
        for q in queries:
            if q.partition_group is not None:
                groups[q.partition_group] = max(
                    groups.get(q.partition_group, 0.0), q.epsilon
                )
        return total + sum(groups.values())

    def total_epsilon_zcdp(self) -> float:
        """zCDP accounting: pure eps-DP -> rho = eps^2 / 2, rho adds, then
        convert back to epsilon at the accountant's delta. Tighter than basic
        composition when many small sequential queries are involved."""
        rho = 0.0
        groups: dict[str, float] = {}
        for q in self._queries:
            if q.partition_group is None:
                rho += q.epsilon ** 2 / 2.0          # sequential rho adds
            else:                                     # parallel: keep worst
                groups[q.partition_group] = max(
                    groups.get(q.partition_group, 0.0), q.epsilon
                )
        rho += sum(e ** 2 / 2.0 for e in groups.values())
        # (eps, delta) conversion: eps = rho + 2*sqrt(rho * ln(1/delta))
        return rho + 2.0 * math.sqrt(rho * math.log(1.0 / self.delta))

Verification # permalink

The check confirms the cumulative ε never exceeds the cap and that parallel grouping behaves as expected.

acct = PrivacyBudgetAccountant(budget_cap=1.0, delta=1e-6)

# Three H3 resolution tiers over the SAME people -> sequential, they sum.
acct.spend(SpatialQuery("density_r7", 0.3))
acct.spend(SpatialQuery("density_r8", 0.3))
acct.spend(SpatialQuery("density_r9", 0.4))

# Verify sequential sum and the hard cap invariant.
assert abs(acct.total_epsilon_basic() - 1.0) < 1e-9
assert acct.total_epsilon_basic() <= acct.budget_cap + 1e-12

# A fourth overlapping query must be refused (would reach 1.1 > cap).
try:
    acct.spend(SpatialQuery("density_r10", 0.1))
    raise AssertionError("cap breach was not caught")
except ValueError:
    pass  # expected: budget guard fired

# Disjoint cells in one group cost only the max, not the sum.
par = PrivacyBudgetAccountant(budget_cap=0.5)
for i, eps in enumerate([0.3, 0.3, 0.2]):
    par.spend(SpatialQuery(f"cell_{i}", eps, partition_group="grid_r8"))
assert abs(par.total_epsilon_basic() - 0.3) < 1e-9  # max, not 0.8
print("all budget-composition checks passed")

Edge Cases & Adjustments # permalink

• Overlapping extents masquerading as disjoint. Parallel composition is only valid when partitions are record-disjoint. Buffered radii, sliding windows, and nested resolutions overlap — treat them as sequential. When in doubt, assign partition_group=None and pay the sum; it is the conservative, sound choice.

• Repeated daily queries. A map refreshed against a rolling window re-reads each person every day, so budget accumulates linearly. Bound the horizon explicitly (for example a 30-day cap), cache and re-serve noisy releases instead of recomputing, or apply a retention window so old contributions age out of the accounting.

• Adaptive queries. Composition theorems hold even when a later query’s ε, resolution, or extent is chosen from earlier noisy outputs, so the accounting stays valid. But adaptivity voids independence assumptions for utility estimates — never reclassify an adaptively selected extent as a disjoint partition.

• Mixing mechanisms. If some releases use Gaussian noise, convert everything to ρ (ρ = Δf²/(2σ²) for Gaussian, ρ = ε²/2 for pure-DP) before adding, then convert the accumulated ρ to (ε, δ) once at report time. Per-tier ε values still guide allocation, as when setting epsilon values for spatial heatmap generation.

FAQ # permalink

When can I use parallel composition instead of summing epsilon?

Only when the queries operate on disjoint subsets of records. Because every individual contributes to exactly one partition, the worst-case privacy loss is the maximum ε across partitions rather than the sum. Non-overlapping grid cells, disjoint H3 hexagons, and mutually exclusive time buckets qualify. Overlapping radii and nested resolutions do not — for those, sum the ε.

Why does zCDP give a tighter cumulative bound than basic composition?

Basic composition adds ε linearly, assuming every query realizes its worst case at once. Zero-concentrated DP tracks a single ρ that adds cleanly, then converts to (ε, δ) with a square-root term, so cumulative ε for many small queries grows like √k rather than k. The advantage only materializes when per-query ε is small; for a handful of large queries, basic composition can actually report a smaller number.

Do repeated daily refreshes of the same map consume budget every day?

Yes. Each refresh that re-reads the underlying dataset is a fresh sequential query. A map refreshed daily at ε = 0.1 reaches a budget of 3.0 in thirty days under basic accounting. Bound the horizon, cache noisy releases, or apply a fixed retention window so budget does not accumulate without limit.

How do adaptive queries affect composition?

They do not break the ε accounting — composition theorems hold even when later queries depend on earlier noisy outputs. They do break the independence assumptions used for utility modeling, so treat any adaptively chosen resolution or extent as sequential, never as a disjoint partition.

Related

• Privacy Budget Allocation for Spatial Queries — parent guide to allocating and tracking epsilon across a pipeline
• Setting Epsilon Values for Spatial Heatmap Generation — per-tier budget allocation for multi-resolution heatmaps
• Applying Laplace Noise to Latitude/Longitude Pairs — the noise mechanism each composed release calibrates
• Differential Privacy for Location Data — foundations of epsilon, sensitivity, and mechanisms

← Back to Privacy Budget Allocation for Spatial Queries