Small-Cell Suppression & Complementary Suppression Rules

Suppressing a map cell whose count falls below a threshold is the oldest control in statistical disclosure, and on its own it almost never works: if the release also publishes a district total, a reader subtracts the visible cells and recovers the withheld one exactly. Complementary suppression is the step that withholds enough additional cells to make that subtraction underdetermined.

Why Primary Suppression Leaks # permalink

A choropleth or grid release usually carries more than the cells themselves. It carries a regional total, a time-series total, a “total across all categories” column, or simply a neighbouring release at a coarser resolution that a reader can difference against. Each of those is a linear equation over the cell values.

Withholding one cell from a row whose total is published leaves a single equation in a single unknown. The suppression is visible, the total is visible, and the arithmetic is trivial. Statistical agencies have called this the complementary suppression problem for decades, and the same failure reappears in every generation of mapping tools because the primary rule — drop cells under $k$ — is so obviously correct that nobody checks whether it is sufficient.

The consequence for spatial releases is sharper than for ordinary tables, because a map’s marginals are geographic and readers already have them. Administrative boundaries nest: block into tract, tract into district, district into region. Publishing any two levels of that hierarchy publishes the differences between them, and the differences are exactly the suppressed small cells.

Algorithmic Specification # permalink

The primary rule # permalink

Let $n_c$ be the count in cell $c$ and $k$ the minimum publishable count. The primary suppression set is

Cells with $n_c = 0$ are usually publishable, because a true zero discloses nothing about an individual — though see the caveat below on structural versus sampling zeros.

The protection condition # permalink

Let the release also publish a set of linear constraints $\mathcal{L}$ — row totals, column totals, hierarchy totals — where each $L \in \mathcal{L}$ is an equation $\sum_{c \in L} n_c = T_L$. A suppression set $S \supseteq S_1$ is safe when, for every primary cell $c \in S_1$ and every constraint $L$ containing $c$:

That is, no published equation may contain exactly one unknown. This is the minimal condition; a stronger one bounds how tightly the remaining system brackets each unknown.

The interval attack # permalink

Even when every equation holds two or more unknowns, a reader can compute a feasible interval for each suppressed cell by linear programming, using non-negativity and any published upper bounds:

The cell is genuinely protected only when the width $n_c^{\max} - n_c^{\min}$ exceeds a stated protection level $p$. A suppression set that satisfies the two-unknowns rule but yields an interval of width 1 has published the value.

Choosing the complements # permalink

Selecting the additional cells is an optimisation: minimise information lost, subject to the safety condition. The standard objective is total suppressed count,

which is an integer program in general. In practice a greedy heuristic — for each unsafe equation, suppress the smallest additional cell that also appears in another unsafe equation — gets close and is far easier to reason about in a release pipeline.

Parameter reference # permalink

Prerequisites & Data Requirements # permalink

• A complete inventory of published totals. This is the step teams skip. Every aggregate the organisation publishes from the same source is a constraint, including ones published by a different team, at a different resolution, or last year. A total you forgot about is an equation the reader still has.
• Counts of distinct individuals, not rows. The threshold is about people; a cell with forty taps from three riders fails the test even though the row count passes. The same distinction governs k-anonymity grouping for location traces.
• A stable cell geometry across releases. If the grid origin moves between publications, the two releases differ in ways that let a reader difference them — the mechanism described under grid aggregation and spatial binning strategies.
• A decision about zeros, written down. A structural zero (no residential land in the cell) is safe to publish. A sampling zero (nobody was observed, but people live there) is a statement about a small population and often is not.
• Python dependencies. numpy and pandas for the tables, scipy.optimize.linprog for the interval bounds, geopandas if the constraints follow administrative geometry.

Step-by-Step Implementation # permalink

Step 1 — Enumerate every constraint the release exposes # permalink

import pandas as pd

def constraints_from_release(cells: pd.DataFrame,
                             publish_rows: bool, publish_cols: bool,
                             hierarchy_col: str | None) -> list[list[str]]:
    """Each returned list is the set of cell ids bound by one published total."""
    groups: list[list[str]] = []
    if publish_rows:
        groups += [g["cell_id"].tolist() for _, g in cells.groupby("row_id")]
    if publish_cols:
        groups += [g["cell_id"].tolist() for _, g in cells.groupby("col_id")]
    if hierarchy_col:
        groups += [g["cell_id"].tolist() for _, g in cells.groupby(hierarchy_col)]
    return groups

Step 2 — Apply the primary rule on distinct-person counts # permalink

def primary_suppression(cells: pd.DataFrame, k: int) -> set[str]:
    """Withhold non-empty cells below k distinct individuals."""
    small = cells[(cells["n_persons"] > 0) & (cells["n_persons"] < k)]
    return set(small["cell_id"])

Step 3 — Close every equation that holds a single unknown # permalink

def complementary_suppression(cells: pd.DataFrame, groups: list[list[str]],
                              primary: set[str]) -> set[str]:
    """Greedy: while some published total has exactly one unknown, suppress the
    cheapest additional cell in it, preferring cells that also sit in another
    under-protected total so one suppression can close two equations."""
    cost = cells.set_index("cell_id")["n_persons"].to_dict()
    suppressed = set(primary)
    changed = True
    while changed:
        changed = False
        for g in groups:
            unknown = [c for c in g if c in suppressed]
            if len(unknown) != 1:
                continue
            candidates = [c for c in g if c not in suppressed]
            if not candidates:
                continue                      # whole group already withheld
            overlap = {c: sum(1 for h in groups if c in h) for c in candidates}
            pick = min(candidates, key=lambda c: (cost[c], -overlap[c]))
            suppressed.add(pick)
            changed = True
    return suppressed

Step 4 — Bound each protected cell by linear programming # permalink

import numpy as np
from scipy.optimize import linprog

def feasible_width(cell_ids: list[str], A: np.ndarray, b: np.ndarray,
                   target_index: int) -> float:
    """Width of the interval a reader can derive for one suppressed cell."""
    c = np.zeros(len(cell_ids)); c[target_index] = 1.0
    lo = linprog(c,  A_eq=A, b_eq=b, bounds=[(0, None)] * len(cell_ids))
    hi = linprog(-c, A_eq=A, b_eq=b, bounds=[(0, None)] * len(cell_ids))
    if not (lo.success and hi.success):
        return 0.0
    return float(-hi.fun - lo.fun)

Step 5 — Report the suppression cost before publishing # permalink

A release that withholds a third of its cells is often worse for the reader than a coarser release that withholds none. Compute the suppressed fraction and compare it against the alternative of aggregating up one level, exactly as when choosing grid cell size for population density maps.

Validation & Re-identification Testing # permalink

Run the reader’s attack, not your own rule. Build the full system $An = T$ from the constraints you actually publish, solve for the interval on every suppressed cell, and fail the release if any width falls below the protection level. This catches the case the greedy heuristic misses: a set that satisfies “two unknowns per equation” while the two unknowns are so tightly coupled by other equations that both are determined.

Test across releases as well as within one. Load last quarter’s published table, add its constraints to the system, and re-solve. Cells protected in isolation are routinely determined by the pair, which is the temporal version of the same arithmetic.

Finally, check what the suppression pattern itself says. If small cells cluster — and they do, because sparse populations are spatially clustered — the map of withheld cells is a map of sparse areas. Where that is itself sensitive, the answer is a coarser geometry rather than more suppression.

Common Failure Modes & Gotchas # permalink

Publishing totals as a courtesy. A “regional summary” row added for reader convenience is a constraint. Add it to the system or drop it.

Forgetting the hierarchy. Tract and district releases from the same source difference to block-level values. Suppression has to be computed jointly across every level published.

Suppressing values rather than cells. Replacing a count with null while keeping the row tells the reader the cell was small. Omit the row entirely, as argued under grid aggregation and spatial binning strategies.

Treating zeros as safe by default. A sampling zero in a populated cell says “fewer than one observed person here”, which can be as disclosive as a count of one.

Rounding instead of suppressing. Rounding to the nearest five leaves the true value in a band of width five and is defeated by the same linear algebra, now over rounded totals.

Greedy without verification. The heuristic is fine as a generator and useless as a guarantee. The linear program is what decides whether the release ships.

Building the Constraint Inventory # permalink

The inventory is the step that decides whether any of this works, and it is almost always incomplete on the first attempt. Four categories are routinely missed.

Totals published by another team. A summary figure in an annual report, a headline count in a press release, or a dashboard tile maintained by a different department are all equations over the same cells. They do not appear in the release pipeline and they constrain it anyway.

Earlier releases at another resolution. Any two levels of a nested geography difference to the level between them. A tract release from last year and a district release from this year jointly determine block-level values even though neither publishes them.

Implied bounds. A legend implies a maximum. A record count implies a grand total. A statement that “no cell exceeds 500” is a set of inequalities that narrows every interval the linear program computes. These are constraints even though nobody thinks of them as published totals.

Derived products. A tile service, an API endpoint, a downloadable extract and a printed map may each expose a different aggregation of the same source. If any two are jointly available, their difference is available too.

Compiling the inventory is a governance task rather than an engineering one, and it is the part of this control that cannot be automated: a pipeline can enforce whatever constraint set it is given, and it has no way to discover a constraint that lives in a PDF. Reviewing the inventory on a schedule — the same schedule that re-checks re-identification risk against new auxiliary layers — is what keeps it honest.

Compliance Alignment # permalink

The constraint inventory is the part an assessment most often lacks and the part a regulator can most easily test, because every published total is public by definition.

FAQ # permalink

Is suppression better or worse than adding noise?

They fail differently. Suppression preserves the published values exactly and removes coverage; noise preserves coverage and perturbs every value. For a map whose readers do arithmetic across cells, noise is usually safer because it has no exact-recovery attack — which is the argument for moving to Laplace or Gaussian noise on cell counts once the suppressed fraction climbs.

What threshold should $k$ be?

It follows the sector, not the geometry. Health releases commonly use 11, official statistics a rule of three or five, public mobility feeds considerably more — the values and their reasoning are set out in sector-specific k-anonymity thresholds for location data.

Do I need complementary suppression if I publish no totals?

You almost certainly publish some. A map with a colour scale implies a maximum; a downloadable dataset with a record count implies a grand total; a previous release at a coarser resolution implies every difference. Run the inventory before concluding there are no constraints.

Can the complements be chosen to minimise visual damage rather than count?

Yes, and often they should. Suppressing a large-count cell hurts the arithmetic reader less than it hurts the map reader, so a cartographic release may prefer to suppress several small neighbours instead. Change the objective in the optimisation; the safety condition is unaffected.

Related # permalink

• Setting Minimum Count Thresholds for Published Map Cells — choosing $k$ and $p$ for a specific release
• Applying Complementary Suppression to Choropleth Maps — the greedy pass and the linear-programming check, end to end
• Grid Aggregation & Spatial Binning Strategies — the geometry that decides how many cells fall below the threshold
• l-Diversity & t-Closeness for Spatial Attributes — the complementary problem when the cell contents rather than the counts are sensitive
• Sector-Specific k-Anonymity Thresholds for Location Data — where the threshold comes from

← Back to Geospatial Masking & Perturbation Techniques