โš™๏ธ How-To Privacy & sensitive locations Census & demographics Geoprivacy & Anonymisation ยท step 11 of 20 Updated

How to add differentially private noise to spatial counts

Problem statement

Suppression answers "is this table safe?" once. If you publish the same geography every month for five years, you need an answer that composes โ€” one where running the query again has a cost you can see. That is what a differential privacy budget gives you, and the Laplace mechanism is the three-line implementation.

The code is easy and the accounting is not. Three things have to be decided before any noise is added: what one unit of privacy is, how many cells one unit can affect, and how much total budget the product gets over its lifetime. This guide implements the mechanism on 44 cells of 500 m London crime counts and shows what each choice does to the map.

Quick answer 

import numpy as np

def private_counts(counts, epsilon, sensitivity=1, rng=None):
    """Laplace mechanism: noise scale = sensitivity / epsilon."""
    rng = rng or np.random.default_rng()
    noisy = counts + rng.laplace(0.0, sensitivity / epsilon, size=len(counts))
    return np.maximum(np.round(noisy), 0).astype(int)      # post-processing is free

released = private_counts(cell_counts.values, epsilon=1.0, rng=np.random.default_rng(7))

Measured on the real counts, ฮต=1.0 gave a mean absolute error of 1.03 crimes per cell against a median cell count of 214 โ€” invisible in any use of the map. At ฮต=0.1 the mean error was 11.51, two cells went negative and two non-empty cells were released as zero.

Flow from points through aggregation, sensitivity bounding, Laplace noise and post-processing to a released count layer.
The aggregation step is what makes sensitivity small enough for the mechanism to be usable.

Step-by-step solution

1. State the unit of privacy

Write it in the metadata in words: "adding or removing all records of one person changes the output distribution by at most e^ฮต". If you cannot say that sentence truthfully โ€” because one person contributes many records and you have not bounded it โ€” the ฮต you publish is not the ฮต you have.

2. Bound the sensitivity

Sensitivity is the maximum change one unit can cause across all published cells. For counts where one person appears once, it is 1. For repeat visits or trajectories, clamp the contribution:

def clamp(df, subject, k):
    return df.groupby(subject, group_keys=False).head(k)

clamped = clamp(visits, "patient_id", k=3)     # sensitivity is now 3

The clamp itself is a modelling choice with a bias โ€” it truncates the heaviest users โ€” and belongs in the documentation.

3. Choose ฮต and write down the budget

ฮต is a policy parameter. Decide the total for the product's lifetime, then divide it among the queries you intend to publish. A ledger of two columns โ€” query, ฮต spent โ€” is enough, and it must include the queries you ran to design the product.

4. Add the noise to every cell, including the empty ones

A cell that is omitted because its true count is zero leaks that the count is zero. Build the full cell list from the geography, reindex the counts onto it with zeros, and noise all of them.

counts = observed.reindex(all_cells, fill_value=0)
noisy = private_counts(counts.values, epsilon=1.0)

5. Post-process for usability

Clamping negatives, rounding to integers, smoothing and reconciling a hierarchy so children sum to a parent are all allowed, because none of them looks at the raw data again.

6. Report the accuracy you delivered

Users need to know the noise scale to interpret the map. Publish ฮต, the sensitivity, the noise distribution and the resulting error percentiles at the cell sizes you offer.

7. Check whether the map survived

If the interesting features are small counts, the mechanism will destroy them and no ฮต you can defend will save them. At that point, aggregate to bigger units instead โ€” which is a different, non-private-but-adequate answer, and an honest one.

Stack showing a total epsilon budget split across a monthly map, a category table and a design query.
Everything computed from the raw data spends budget, including the queries that chose the parameters.

Code examples

Example 1 โ€” the accuracy/ฮต curve on real counts 

import numpy as np

rng = np.random.default_rng(7)
counts = cell_counts.values          # 44 cells of 500 m, 19,619 crimes, central London

print(f"{'eps':>5} {'mean |err|':>10} {'p95 |err|':>9} {'negatives':>10} {'true>0 -> 0':>12} {'drift':>8}")
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,} "
          f"{clipped.sum() - counts.sum():+8.0f}")
  eps mean |err| p95 |err|  negatives  true>0 -> 0    drift
  0.1      11.51     44.42          2            2       -3
  0.5       1.75      4.39          0            0      +10
  1.0       1.03      2.96          0            0       -7
  2.0       0.46      1.26          0            0       +6

The smallest true count in these cells was 2 and the largest 3,533, so ฮต=1 leaves the map visually identical and ฮต=0.1 does not.

Example 2 โ€” a budget ledger you can actually keep 

import json, pathlib, datetime

class Budget:
    def __init__(self, total, path="epsilon_ledger.json"):
        self.total, self.path = total, pathlib.Path(path)
        self.spent = json.loads(self.path.read_text()) if self.path.exists() else []

    def remaining(self):
        return self.total - sum(e["epsilon"] for e in self.spent)

    def spend(self, label, epsilon):
        if epsilon > self.remaining():
            raise ValueError(f"{label}: {epsilon} requested, {self.remaining():.3f} left")
        self.spent.append({"label": label, "epsilon": epsilon,
                           "when": datetime.datetime.now().isoformat(timespec="seconds")})
        self.path.write_text(json.dumps(self.spent, indent=2))
        return epsilon

budget = Budget(total=4.0)
eps = budget.spend("2025-Q1 500 m crime map", 1.0)
released = private_counts(counts, eps)
print(f"remaining budget: {budget.remaining():.2f}")

The ledger is the artefact that makes the guarantee real. Without it, "differentially private" describes one run, not a product.

Example 3 โ€” reconciling a hierarchy after noising 

import numpy as np

def reconcile(child_counts, parent_total):
    """Scale noisy children so they sum to a noisy parent, then round to integers."""
    child = np.maximum(child_counts, 0).astype(float)
    if child.sum() == 0:
        return np.zeros_like(child, dtype=int)
    scaled = child * (parent_total / child.sum())
    out = np.floor(scaled).astype(int)
    short = int(parent_total - out.sum())
    if short > 0:                                   # hand the remainder to the largest fractions
        order = np.argsort(-(scaled - out))[:short]
        out[order] += 1
    return out

wards = private_counts(ward_counts, epsilon=0.5)
borough = private_counts(np.array([ward_counts.sum()]), epsilon=0.5)[0]
print(reconcile(wards, borough).sum(), borough)

Both queries spend budget; the reconciliation itself does not, because it only touches the two noisy outputs.

Explanation

Why the noise does not depend on the count

The Laplace scale is sensitivity/ฮต, and sensitivity for a count is how much one person can change it โ€” one. That is independent of whether the cell holds 2 or 3,533. It makes the mechanism nearly free on large counts and fatal on small ones, which is the single most important practical fact about it.

Why every cell must be published

If cells appear in the output only when their true count is non-zero, the presence of a cell is itself a noiseless statistic. Build the cell list from the geography, not from the data.

Why post-processing is free

The guarantee is a property of the mapping from the raw data to the released values. Anything computed from the released values alone cannot increase the information about the raw data, so clamping, rounding and smoothing are safe โ€” and they should be used, because raw Laplace output is unusable.

Why this is often the wrong tool for a map

Maps are interesting where counts are small: the one cluster, the rare category, the quiet ward. Those are exactly the cells noise destroys. If your map's purpose survives ฮต=1 on 500 m cells, use it; if the purpose is to find sparse events, aggregation to units built for the threshold is the better answer. How to aggregate points to units that meet a minimum count covers that route.

Two panels comparing Laplace noise on a cell of 3,533 records and a cell of 2, showing the same absolute error and wildly different relative error.
The mechanism is nearly free on large counts and fatal on small ones.

Edge cases or notes

  • Do not resample negative values. Clamp them; resampling is data-dependent and breaks the guarantee.
  • Do not suppress noisy cells. Suppression after noising reintroduces a raw-data decision.
  • The geometry is public. Only the counts are protected.
  • One person, many cells. Trajectories need a clamp on cells touched, not just on records.
  • Seeds are for reproducibility, not secrecy. Publishing the seed lets a user reproduce the file; it does not weaken ฮต.
  • Composition is additive for pure ฮต. Advanced composition gives a better bound but needs (ฮต, ฮด).
  • Budget the design queries. Choosing a cell size by looking at counts costs ฮต.
  • Small ฮต makes rates nonsense. A noisy numerator over a small denominator can exceed 100%.

FAQ

How much noise should I add?

Scale sensitivity/ฮต. For a count where one person appears once and ฮต=1, that is Laplace with scale 1 โ€” about one count of error per cell.

What ฮต should I use?

There is no correct value; it is a policy choice. Published products range from about 0.1 to 10 in total. Decide the lifetime budget first, then divide it.

Do I add noise to zero-count cells?

Yes. Omitting them publishes the fact that they are zero without any noise at all.

Can I clamp negative counts to zero?

Yes. Post-processing a released value never weakens the guarantee, and raw Laplace output is unusable without it.

What if one person contributes many records?

Clamp to at most k records per person and set sensitivity to k. Without the clamp, one heavy user sets the noise scale for everyone.

Can I combine differential privacy with suppression?

No. Suppressing cells based on their values is a raw-data decision that is not covered by the budget.