Building Differentially Private Heatmaps

A public mobility dashboard that renders a density surface — foot traffic, ride-hail pickups, cycling volume — is one of the easiest ways to leak an individual, because a single bright cell over a quiet cul-de-sac names the person who lives there. This page walks the full end-to-end pipeline to publish a differentially private heatmap: choose a grid resolution, bin points to it, add per-cell Laplace noise, post-process, and normalise for rendering — all under a fixed $\varepsilon$ . It is the concrete, single-artefact recipe inside the differentially private spatial aggregation guide, which frames the general histogram theory, and it sits under the Differential Privacy for Geospatial Data section. Where this page fixes a uniform grid up front, the sibling on private quadtree decomposition adapts cell sizes to density instead; start here when a fixed raster is what your tiling front end already expects.

Parameter Configuration and Calibration

A DP heatmap has exactly three knobs that trade privacy against utility, and every rendering artefact you will ever debug traces back to one of them. Fix them deliberately before writing a line of aggregation code.

The dominant tension is cell size versus relative error. A DP heatmap is a histogram: each grid cell holds a count, and the Laplace mechanism adds noise of scale $b = \Delta f / \varepsilon$ to every cell independently. The absolute noise per cell is constant, so the relative error in a cell with true count $n$ is approximately $b/n$ . Halving the cell edge quarters the area, which roughly quarters the points that land in each cell, which quadruples the relative error at fixed $\varepsilon$ . Coarser cells aggregate more points, dilute the noise, and preserve genuine hotspots; finer cells give sharper geography but drown sparse regions in noise. The whole calibration problem is choosing the coarsest cell your consumers will tolerate.

Parameter	What it controls	Calibration rule
`cell_size`	Spatial resolution; points-per-cell $n$	Set so the median populated cell holds $n \gg b$ . In WGS84, `0.001°` ≈ 110 m; drop to `0.005°` (~550 m) for sparse rural feeds.
`epsilon`	Total privacy budget for the release	Whole-heatmap $\varepsilon$ , debited once from the subject’s ledger. Typical dashboards use $0.5$ – $2.0$ ; smaller $\varepsilon$ needs coarser cells to stay legible.
`max_contrib`	Per-user contribution cap	Bounds L1 sensitivity to $\Delta f = c_{\max}$ . Cap each user to the $c_{\max}$ cells they touch most; noise scale becomes $b = c_{\max}/\varepsilon$ .

The subtle knob is max_contrib. The clean sensitivity of $\Delta f = 1$ holds only when each data subject can influence exactly one cell count — one person, one bucket. Real telemetry violates this: a user with an all-day trace deposits points in dozens of cells, so a single subject’s presence or absence shifts many counts at once, and the true L1 sensitivity is the number of cells they touch. Left unbounded that is potentially the entire grid, forcing catastrophic noise. Contribution capping restores a bound: retain at most $c_{\max}$ cells per user (their most-visited, or a random subset), which caps sensitivity at $c_{\max}$ and sets the noise scale to $b = c_{\max}/\varepsilon$ . Choosing $c_{\max}=1$ recovers the textbook single-cell case at the cost of discarding most of a user’s footprint; $c_{\max}=3$ – $5$ is a common middle ground for mobility feeds. Tie the ceiling to a concrete clause via the compliance framework mapping so the number is defensible, not arbitrary.

Reference Implementation

The function below is the whole pipeline in one place: bin, cap, noise, post-process, normalise. It takes an array of (x, y, user_id) rows so it can enforce the per-user cap that keeps sensitivity bounded, and it returns a noised, non-negative, unit-normalised 2-D density array ready to hand to a colour ramp. The clamp, the optional smoothing, and the normalisation are all post-processing — they touch only the already-noised counts, so by the post-processing immunity of differential privacy they consume zero additional budget.

python

from __future__ import annotations

import numpy as np
from numpy.typing import NDArray
from typing import Tuple

def dp_heatmap(
    points: NDArray[np.float64],   # shape (N, 3): columns [x, y, user_id]
    bounds: Tuple[float, float, float, float],  # (min_x, min_y, max_x, max_y)
    cell_size: float,
    epsilon: float,
    max_contrib: int,
    *,
    smooth: bool = False,
    seed: int | None = None,
) -> NDArray[np.float64]:
    """Publish a differentially private density surface over a fixed grid.

    Pipeline: bin points -> cap each user to max_contrib cells (bounds L1
    sensitivity) -> add per-cell Laplace noise scale max_contrib/epsilon
    -> clamp >= 0 -> optional smoothing -> normalise to [0, 1].

    The whole release spends exactly `epsilon` once. Everything after the
    noise step is post-processing and is budget-free.
    """
    if epsilon <= 0 or cell_size <= 0 or max_contrib < 1:
        raise ValueError("epsilon, cell_size > 0 and max_contrib >= 1 required")
    min_x, min_y, max_x, max_y = bounds
    n_cols = int(np.ceil((max_x - min_x) / cell_size))
    n_rows = int(np.ceil((max_y - min_y) / cell_size))
    rng = np.random.default_rng(seed)

    # 1. Map each point to a (row, col) cell, dropping anything out of bounds.
    x, y, uid = points[:, 0], points[:, 1], points[:, 2].astype(np.int64)
    col = np.floor((x - min_x) / cell_size).astype(np.int64)
    row = np.floor((y - min_y) / cell_size).astype(np.int64)
    inside = (col >= 0) & (col < n_cols) & (row >= 0) & (row < n_rows)
    col, row, uid = col[inside], row[inside], uid[inside]

    # 2. Contribution capping: keep <= max_contrib DISTINCT cells per user so a
    #    single subject can move at most max_contrib counts -> L1 sensitivity cap.
    counts = np.zeros((n_rows, n_cols), dtype=np.float64)
    flat = row * n_cols + col
    order = np.argsort(uid, kind="stable")
    uid_s, flat_s = uid[order], flat[order]
    _, starts = np.unique(uid_s, return_index=True)
    for a, b in zip(starts, np.append(starts[1:], len(uid_s))):
        user_cells = np.unique(flat_s[a:b])            # distinct cells this user hit
        if user_cells.size > max_contrib:              # over the cap -> subsample
            user_cells = rng.choice(user_cells, max_contrib, replace=False)
        r, c = np.divmod(user_cells, n_cols)
        counts[r, c] += 1.0                            # each retained cell gets +1

    # 3. Laplace mechanism: sensitivity is max_contrib, so scale b = c_max/eps.
    #    This is the ONLY step that spends privacy budget.
    scale = max_contrib / epsilon
    noised = counts + rng.laplace(loc=0.0, scale=scale, size=counts.shape)

    # 4. Post-processing (budget-free): clamp negatives that noise created, then
    #    optionally smooth. Clamping is safe because it is a function of the
    #    already-private output and never re-reads the raw data.
    noised = np.maximum(noised, 0.0)
    if smooth:                                         # 3x3 box blur, edge-safe
        k = np.ones((3, 3)) / 9.0
        padded = np.pad(noised, 1, mode="edge")
        noised = np.stack([
            padded[i:i + n_rows, j:j + n_cols]
            for i in range(3) for j in range(3)
        ]).T.dot(k.ravel()).T

    # 5. Normalise to [0, 1] for a colour ramp. Also post-processing.
    peak = noised.max()
    return noised / peak if peak > 0 else noised

Two design choices carry the privacy weight. First, capping operates on distinct cells per user, not raw points — a user who pings the same cell 400 times still contributes at most +1 to it, which is what makes the “user-in-one-cell” count have sensitivity 1 and the capped case sensitivity $c_{\max}$ . Second, nothing after step 3 ever looks at points again; clamp, blur, and normalise are pure functions of the noised array, which is why they are free. Smoothing is genuinely a free lunch for utility here: a 3×3 box blur averages out some of the per-cell noise without spending a cent of budget, at the cost of a little spatial sharpness.

Validation Checkpoint

A DP heatmap can look plausible while silently violating its guarantee — a forgotten cap inflates sensitivity, a normalise-before-noise ordering leaks, a stray negative crashes a renderer. Assert the invariants below in CI with a fixed seed so a regression fails the build rather than shipping. The harness plants a hotspot far above the noise floor and confirms it survives, checks non-negativity, and bounds total mass to the analytic noise band.

python

def _validate() -> None:
    rng = np.random.default_rng(7)
    bounds = (0.0, 0.0, 4.0, 4.0)           # a 4x4 grid at cell_size 1.0
    cell_size, epsilon, max_contrib = 1.0, 1.0, 1

    # Build points: uniform background + a planted hotspot in cell (row 1, col 2).
    bg = np.column_stack([
        rng.uniform(0, 4, 600), rng.uniform(0, 4, 600), np.arange(600),
    ])
    hot = np.column_stack([                 # 400 distinct users, all in one cell
        rng.uniform(2, 3, 400), rng.uniform(1, 2, 400), np.arange(600, 1000),
    ])
    points = np.vstack([bg, hot])

    grid = dp_heatmap(points, bounds, cell_size, epsilon, max_contrib, seed=1)

    # 1. Non-negativity: post-clamp output must never be negative.
    assert (grid >= 0).all(), "clamp failed: negative density leaked to render"

    # 2. Hotspot survival: the planted cell must remain the global maximum.
    peak_cell = np.unravel_index(int(grid.argmax()), grid.shape)
    assert peak_cell == (1, 2), f"hotspot did not survive, argmax={peak_cell}"

    # 3. Hotspot dominance / sparse-cell swamping: with a true count of 400
    #    against a noise scale b = c_max/eps, the hotspot normalises to 1.0 while
    #    every background cell (true count ~40) stays well below it. No other cell
    #    may cross half the peak, or a phantom hotspot has appeared.
    b = max_contrib / epsilon
    others = grid.copy()
    others[peak_cell] = 0.0
    assert grid[peak_cell] == 1.0, "peak must normalise to 1.0"
    assert others.max() < 0.5, f"phantom hotspot: runner-up={others.max():.2f}"

    # 4. Mass band: the sum over C cells of Laplace(b) noise has std b*sqrt(2C),
    #    so aggregate error is small even though per-cell error is not. The band
    #    must be a fraction of the true total mass for the release to be useful.
    C = grid.size
    band = 5.0 * b * np.sqrt(2.0 * C)
    true_total = 1000.0                      # every user retained in exactly 1 cell
    assert band < 0.25 * true_total, "noise band too wide for this cell size / eps"

    print("DP heatmap invariants hold: non-negative, hotspot survives, mass bounded")

if __name__ == "__main__":
    _validate()

The mass check encodes the core intuition of sparse-cell swamping: the noise standard deviation on the total grows only as $b\sqrt{2C}$ , so aggregate counts stay accurate, but any individual cell carries the full per-cell $b$ . A cell with true count 2 and $b=1$ has a relative error near 100 %; the planted hotspot with count 400 has relative error under 1 % and therefore survives as the argmax with overwhelming probability. If your validation ever shows the hotspot not surviving, the cells are too fine for the budget — coarsen cell_size or raise $\varepsilon$ .

Incident Response and Edge Cases

DP heatmaps fail in a handful of characteristic ways, most of them at the boundary between the DP step and the rendering step.

Phantom hotspots in empty regions. A sparse or empty cell receives a large positive Laplace draw and renders as a bright spot over open water or a car park, misleading analysts and occasionally implying activity where a single home sits. Detection: monitor the fraction of the surface above a display threshold against the known populated footprint. Remediation: coarsen cell_size so background cells accumulate real mass, apply the free smoothing pass to average phantoms down, or gate the colour ramp with a minimum-count floor derived from $b$ — never by re-reading the raw counts, which would break the guarantee.
Sensitivity blow-up from uncapped users. A power user whose trace touches 200 cells makes the true L1 sensitivity 200, so a pipeline that hard-codes $b=1/\varepsilon$ is silently under-noising and out of compliance. Detection: assert max_contrib is enforced and log the distribution of distinct cells per user. Remediation: set max_contrib explicitly and set noise scale to max_contrib/epsilon; the two numbers must always move together.
Post-processing that peeks at raw data. An engineer adds a “smart” clamp that snaps low cells to their true zero, or normalises against the raw peak — reintroducing a dependence on private data and voiding the release. Detection: code review for any reference to the un-noised counts after the noise line. Remediation: enforce that every step after the Laplace draw is a pure function of the noised array only, exactly as the spatial noise mechanisms guide requires.
Budget double-spend across refreshes. A live dashboard that regenerates the heatmap hourly from the same population spends $\varepsilon$ every refresh, and cumulative spend explodes. Detection: an $\varepsilon$ ledger that flags repeated releases over an unchanged cohort, per the privacy budget management guide. Remediation: cache one release per epoch, or use a streaming mechanism designed for repeated publication rather than re-running the static pipeline.

Frequently Asked Questions

Why does clamping to zero not cost any privacy budget?

Differential privacy is immune to post-processing: any function applied to a private output, with no further access to the raw data, keeps the same guarantee. The clamp reads only the already-noised array and maps negatives to zero, so it spends nothing. The same holds for the smoothing pass, the rounding, and the normalisation — the entire tail of the pipeline after the Laplace draw is free, which is why you should push as much utility recovery as possible into it.

How do I stop noise from swamping the sparse parts of the map?

You cannot reduce the per-cell noise without spending more budget, so the lever is aggregation: choose a coarser cell size so each populated cell holds many more points, which shrinks the relative error b/n. A free smoothing pass averages neighbouring noise and helps further. Genuine hotspots — cells whose true count is far above the noise scale b — survive at almost any reasonable setting; it is only the sparse set of low-count cells that is unrecoverable, and coarsening is the honest fix.

When is the query sensitivity actually 1 versus max_contrib?

Sensitivity is 1 only when each data subject can influence exactly one cell count — one user contributes to one bucket. As soon as a user's trace spans multiple cells, adding or removing that user shifts several counts, and the L1 sensitivity equals the number of cells they can touch. Contribution capping bounds that to max_contrib, so the correct Laplace scale is max_contrib/epsilon. Setting max_contrib to 1 recovers the clean single-cell case but discards most of each user's footprint.

Should I use a fixed grid or an adaptive quadtree for my heatmap?

A fixed uniform grid, covered here, is the right default when your tiling front end expects a regular raster and density is roughly even. When density varies sharply across the map — dense downtown, empty periphery — a fixed grid either over-noises the sparse regions or under-resolves the dense ones, and an adaptive private quadtree that splits cells only where data warrants gives better utility for the same budget. See the private quadtree decomposition guide for that construction.

Differentially Private Spatial Aggregation — the parent guide on private histograms and count releases that this end-to-end recipe instantiates.
Private Quadtree Decomposition for Spatial Histograms — the adaptive alternative when density varies too sharply for a uniform grid.
Spatial Noise Mechanisms — how the Laplace scale $b = \Delta f / \varepsilon$ is derived and calibrated for spatial counts.
Privacy Budget Management — tracking cumulative $\varepsilon$ so repeated heatmap refreshes do not double-spend.
Compliance Framework Mapping — tying the cell size and $\varepsilon$ ceiling to a concrete regulatory clause.

Up: Differentially Private Spatial Aggregation · Differential Privacy for Geospatial Data