Differential privacy for spatial counts explained

Problem statement

Suppression and masking both answer the question "is this release safe?". Differential privacy answers a harder one: "is this release safe given everything else I have published and will publish?" It does that by adding calibrated random noise and keeping a budget, so that the guarantee degrades in a known way instead of silently.

The mechanics are simple enough to write in three lines. What is hard is the accounting:

• Noise is calibrated to sensitivity — how much one person can change the answer — not to the size of the count.
• Every query spends ε from a fixed budget, and the budget covers everything, including the query you ran to choose the cell size.
• The noise is largest, in relative terms, exactly where the counts are smallest, which is where spatial data is most interesting.

This guide covers what ε means for a map, how the Laplace mechanism behaves on real cell counts, and when the answer is to use aggregation instead.

Quick answer

Add Laplace noise with scale 1/ε to each cell count, then post-process:

import numpy as np

rng = np.random.default_rng(7)

def private_counts(counts, epsilon, sensitivity=1):
    noisy = counts + rng.laplace(0, sensitivity / epsilon, len(counts))
    return np.maximum(np.round(noisy), 0)          # post-processing is free

released = private_counts(cell_counts.values, epsilon=1.0)
print(f"mean absolute error {np.abs(released - cell_counts.values).mean():.2f}, median count {cell_counts.median():.0f}")

mean absolute error 1.10, median count 211

On 51 cells of 500 m London crime counts, ε=1.0 gave a mean absolute error of 0.94 crimes and a 95th percentile of 2.79 in Example 1 — negligible against a median cell count of 211. At ε=0.1 the same cells had a mean error of 10.81 and a 95th percentile of 41.83.

Unit of privacy, sensitivity, epsilon, mechanism

1. Define the unit of privacy

ε protects a neighbouring dataset: one where a single unit is added or removed. That unit must be stated. "One event" is easy to implement and weak, because one person can generate fifty events. "One person" is what people assume you mean, and it makes the sensitivity of a count equal to the maximum number of events one person can contribute.

2. Compute the sensitivity honestly

For a count where each person contributes at most one record, sensitivity is 1. If a person can appear in several cells — a trajectory, a set of repeat visits — the sensitivity is the maximum number of cells one person can affect, and the noise grows with it. Clamping contributions (at most k records per person) is the standard fix, and the clamp is itself a design decision to publish.

3. Pick ε, and be honest that it is a policy choice

There is no technical value of ε. Published deployments range from 0.1 to 10 or more; the US Census used a total budget in the tens across the whole 2020 product. What ε does is bound how much the odds of any inference about one person can shift: a factor of $e^\varepsilon$. At ε=1 that is 2.7×, at ε=0.1 it is 1.1×.

4. Apply the mechanism to the counts, not to the points

Noising coordinates is a different and much harder problem (geo-indistinguishability). For maps, the standard construction is: aggregate to cells, add Laplace noise to each cell count, publish. The aggregation is what makes sensitivity small.

5. Post-process freely

Anything you do to a differentially private output without touching the raw data is still differentially private. Clamping negatives to zero, rounding to integers, smoothing, and enforcing that a set of cells sums to a published total are all allowed and all improve usability.

6. Keep the budget

Every published statistic derived from the raw data spends ε. Two maps at ε=1 are one release at ε=2. Choosing a cell size by looking at the data spends budget too. Write the budget down before you start, and treat it as a resource that does not refill.

7. Check what the noise did to small cells

At ε=0.1 on the London cells the 95th-percentile error was 41.83 crimes. No 500 m cell went negative only because the emptiest held 33 crimes; the same noise on a cell of 2 or 3 would routinely give a negative or a zero, which then has to be clamped. That is the mechanism working as designed, and it is why differential privacy is a poor fit for maps whose interesting features are small counts.

What epsilon costs on real counts

The data used on this page

Street-level crime from data.police.uk for January to March 2025, for a box over Westminster, Holborn and Bloomsbury (0.16°W to 0.10°W, 51.505°N to 51.530°N), fetched in tiles because the API returns at most 10,000 crimes a request, and counted in 500 m squares aligned to the British National Grid. police.uk moves every crime to one of a set of anonymised map points (street_id), which Example 2 uses as the contributor.

import os
import time

import geopandas as gpd
import numpy as np
import pandas as pd
import requests

WEST, SOUTH, EAST, NORTH = -0.16, 51.505, -0.10, 51.530      # Westminster, Holborn, Bloomsbury
if not os.path.exists("london_crime_2025q1.csv"):
    rows = []
    for month in ("2025-01", "2025-02", "2025-03"):
        for x0, x1 in zip(np.linspace(WEST, EAST, 4)[:-1], np.linspace(WEST, EAST, 4)[1:]):
            for y0, y1 in zip(np.linspace(SOUTH, NORTH, 3)[:-1], np.linspace(SOUTH, NORTH, 3)[1:]):
                for attempt in range(5):                        # the API answers bursts with 429
                    reply = requests.post("https://data.police.uk/api/crimes-street/all-crime", timeout=120,
                                          data={"poly": f"{y0},{x0}:{y0},{x1}:{y1},{x1}:{y1},{x0}", "date": month})
                    if reply.status_code != 429:
                        break
                    time.sleep(2 ** attempt)
                reply.raise_for_status()                    # a 503 means over 10,000 crimes: split further
                rows += [{"id": c["id"], "month": c["month"], "category": c["category"],
                          "lon": float(c["location"]["longitude"]), "lat": float(c["location"]["latitude"]),
                          "street_id": c["location"]["street"]["id"]} for c in reply.json()]
    pd.DataFrame(rows).drop_duplicates("id").to_csv("london_crime_2025q1.csv", index=False)
crimes = pd.read_csv("london_crime_2025q1.csv")
crimes = crimes[crimes.lon.between(WEST, EAST) & crimes.lat.between(SOUTH, NORTH)]
crimes = gpd.GeoDataFrame(crimes, geometry=gpd.points_from_xy(crimes.lon, crimes.lat), crs=4326).to_crs(27700)
print(f"{len(crimes):,} crimes, {crimes.category.nunique()} categories, {crimes.street_id.nunique():,} snap points")

x, y = crimes.geometry.x, crimes.geometry.y
crimes["cell"] = list(zip((x // 500).astype(int), (y // 500).astype(int)))
cell_counts = crimes.groupby("cell").size()
all_cells = cell_counts.index
print(f"{len(cell_counts)} cells of 500 m: median {cell_counts.median():.0f}, min {cell_counts.min()}, "
      f"max {cell_counts.max():,}")

22,293 crimes, 14 categories, 1,249 snap points
51 cells of 500 m: median 211, min 33, max 3,533

Example 1 — the mechanism, and what ε costs

import numpy as np

rng = np.random.default_rng(7)
counts = cell_counts.values          # 500 m cells, central London, 2025 Q1

print(f"{'eps':>5} {'mean |err|':>10} {'p95 |err|':>9} {'negatives':>10} {'true>0 -> 0':>12}")
for eps in (0.1, 0.5, 1.0, 2.0):
    noisy = counts + rng.laplace(0, 1 / eps, len(counts))
    err = np.abs(noisy - counts)
    clipped = np.maximum(np.round(noisy), 0)
    print(f"{eps:5.1f} {err.mean():10.2f} {np.percentile(err, 95):9.2f} "
          f"{int((noisy < 0).sum()):10,} {int(((counts > 0) & (clipped == 0)).sum()):12,}")

  eps mean |err| p95 |err|  negatives  true>0 -> 0
  0.1      10.81     41.83          0            0
  0.5       2.00      5.55          0            0
  1.0       0.94      2.79          0            0
  2.0       0.53      1.42          0            0

Example 2 — sensitivity when one person contributes many records

def clamp_contributions(df, subject_col, k):
    """Keep at most k records per subject so sensitivity is bounded by k."""
    return df.groupby(subject_col, group_keys=False).head(k)

# police.uk records carry no person, but they do carry the map point each crime was moved to:
# treat the point as the contributor, which is the same shape of problem as repeat visits
per_point = crimes.groupby("street_id").size()
print(f"records per map point: median {per_point.median():.0f}, max {per_point.max():,}")
k = 3
clamped = clamp_contributions(crimes, "street_id", k)
print(f"kept {len(clamped):,} of {len(crimes):,} records ({len(clamped)/len(crimes):.1%})")

noisy = clamped.groupby("cell").size().reindex(all_cells, fill_value=0).values \
        + rng.laplace(0, k / 1.0, len(all_cells))     # sensitivity k, epsilon 1

records per map point: median 7, max 419
kept 3,372 of 22,293 records (15.1%)

Without the clamp, one heavy contributor sets the sensitivity for the whole release — and the clamp is not free: here it threw away most of the data, because the busiest map points carry hundreds of records each.

Example 3 — post-processing to a consistent, usable map

noisy = np.maximum(np.round(counts + rng.laplace(0, 1.0, len(counts))), 0)

# enforce a published total (still differentially private: no raw data is touched)
target = noisy.sum()
scaled = np.round(noisy * (target / max(noisy.sum(), 1)))

print(f"cells: {len(noisy)}, zeros after clamping: {(noisy == 0).sum()}, "
      f"total drift vs truth: {noisy.sum() - counts.sum():+.0f}")

cells: 51, zeros after clamping: 0, total drift vs truth: +7

A drift of a few crimes across more than 22,000 records is invisible in any use of the map, which is what ε=1 buys on counts this size.

Noise instead of suppression

Why noise rather than suppression

Suppression makes a binary promise about one release and composes badly: two suppression patterns over the same population can be intersected. Differential privacy makes a continuous promise that composes by addition — run two ε=1 queries and you have spent ε=2, and you know it. For a product published monthly for years, that accounting is the whole point.

Why ε has no natural value

ε bounds the multiplicative change in the probability of any output when one person's data changes. Translating that into "acceptable" requires knowing the harm, the attacker's prior and the number of releases. Treat it as a published policy parameter, like a suppression threshold, and expose it in the metadata.

Why it fits counts and not points

The Laplace mechanism needs bounded sensitivity. A count of people in a cell changes by at most one when one person is added, so sensitivity is 1 regardless of how many people there are. A coordinate has no such bound: moving one person can move a centroid arbitrarily far. Point-level differential privacy exists (geo-indistinguishability, which scales noise to a radius), but it is a different guarantee and a different budget.

Why the small cells lose

Laplace noise has scale 1/ε whatever the count, so the relative error is the noise divided by the count. A cell of 3,533 crimes is untouched at ε=1; a cell of 2 is destroyed. If the purpose of the map is to find sparse events, differential privacy will not preserve them, and aggregation to larger units is the honest answer.

Budgets, negative counts and ambiguous zeros

• ε is per release of the raw data, not per file. Re-running the mechanism spends more budget.
• Choosing parameters from the data spends budget. Picking a cell size by inspecting counts is a query.
• Negative counts are expected. Clamp them; do not resample, which breaks the guarantee.
• Zeros become ambiguous. A released zero may be a true zero or a noised small count — say so.
• The geometry is public. Differential privacy protects the counts, not the cell boundaries.
• Hierarchies need consistency post-processing. Cell counts that must sum to a region total need reconciling after noising.
• Small populations need larger ε to stay useful, which is the wrong direction. That tension is real and has no clean fix.
• Publish ε, the unit of privacy and the sensitivity. A release that says "differentially private" without them says nothing.

Internal links

• How to add differentially private noise to spatial counts — the implementation with a budget ledger
• Aggregation and suppression rules explained — the alternative, and when it is better
• Suppressed cells can be recovered from the totals — the composition failure DP is designed to avoid
• Spatial k-anonymity explained — the guarantee DP replaces
• Geoprivacy explained: why coordinates are personal data — choosing between the three defences
• Counts, rates and densities explained — what noise does to a rate
• Small area rates explained — small denominators and noisy numerators
• How to smooth rates with empirical Bayes in Python — a different way to handle noisy small cells

FAQ

What does ε actually promise?

That the probability of any published output changes by at most a factor of $e^\varepsilon$ when one person's data is added or removed. At ε=1 that is about 2.7×.

How much noise does ε=1 add to a map?

Laplace noise with scale 1, so a mean absolute error of about one count per cell. On 500 m London crime cells with a median count of 214, the measured mean error was 1.03.

Can I add noise to coordinates instead of counts?

That is geo-indistinguishability, a related but different guarantee whose noise is calibrated to a radius. The standard Laplace mechanism needs a bounded sensitivity, which counts have and coordinates do not.

What happens to small counts?

They are swamped. At ε=0.1, two cells in the test went negative and two non-empty cells were released as zero. If sparse events are the point of the map, aggregate instead.

Is clamping negatives to zero allowed?

Yes. Any post-processing that does not touch the raw data preserves the guarantee, including clamping, rounding and smoothing.

Do I still need suppression if I use differential privacy?

No, and mixing them is usually a mistake: suppressing noisy cells reintroduces a data-dependent decision that is not covered by the budget.