Building Quadtree Adaptive Grids for Uneven Density

A uniform grid over a city is wrong in both directions at once: too coarse downtown to be useful, too fine in the periphery to be publishable. A quadtree fixes both by subdividing only where the population supports it — and introduces one new risk, which is that the shape of the grid itself leaks the density it was built from.

Core Calculation # permalink

Start from a root cell covering the study area. Recursively split a cell into four quadrants when both conditions hold:

The $4k$ threshold is the key: splitting a cell with $n$ points produces four children whose counts sum to $n$, so a cell must hold at least $4k$ for all four children to have a chance of clearing the k-anonymity floor. Splitting at exactly $k$ guarantees suppression.

Even $4k$ does not guarantee it, because the split is geometric and the population is not. So the recursion must be able to undo itself:

If any child falls below $k$, discard all four and keep the parent. This split-and-rollback structure is what makes the resulting grid safe by construction rather than safe after a suppression pass.

The structural leak is the part that is easy to miss. If the split decision uses true counts, then the published grid geometry is a function of the private data: a small cell in an otherwise coarse area announces “at least $4k$ people live in this 60-metre square”, which is an inference the released counts were supposed to control. Under a differential-privacy claim the split must be made on noised counts, and the noise used for splitting spends budget:

A 30/70 split between structure and counts is a common starting point.

Worked numeric example # permalink

A city of 240 000 residents, $k = 10$, so split threshold $4k = 40$, $D_{\max} = 9$, root cell 32 km square.

The tree stops of its own accord at depth 7 in the dense core and at depth 3 in the periphery, producing 3 982 leaf cells whose counts range from 10 to about 90 — a factor of nine, against a factor of several thousand for a uniform 250 m grid over the same area. The uniform grid at 250 m would have 16 384 cells of which roughly 11 000 fall below $k = 10$ and are suppressed, discarding 68 % of the map to protect 4 % of the population.

Python Implementation # permalink

from __future__ import annotations

from dataclasses import dataclass, field

import numpy as np


@dataclass
class QuadCell:
    x0: float
    y0: float
    x1: float
    y1: float
    depth: int
    count: int
    children: list["QuadCell"] = field(default_factory=list)

    @property
    def is_leaf(self) -> bool:
        return not self.children

    def quadrants(self) -> list[tuple[float, float, float, float]]:
        mx, my = (self.x0 + self.x1) / 2, (self.y0 + self.y1) / 2
        return [(self.x0, self.y0, mx, my), (mx, self.y0, self.x1, my),
                (self.x0, my, mx, self.y1), (mx, my, self.x1, self.y1)]


def build_quadtree(points: np.ndarray, extent: tuple[float, float, float, float],
                   k: int = 10, max_depth: int = 9,
                   epsilon_structure: float | None = None,
                   rng: np.random.Generator | None = None) -> QuadCell:
    """Subdivide only where the population supports it, and roll back if not.

    When `epsilon_structure` is given, split decisions are made on noised
    counts. Without it, the grid geometry is a function of the true data and
    a small cell publicly asserts that at least 4k people live inside it.
    """
    rng = rng or np.random.default_rng()
    x0, y0, x1, y1 = extent
    per_level = (epsilon_structure / max_depth) if epsilon_structure else None

    def observed(n: int) -> float:
        if per_level is None:
            return float(n)
        return n + rng.laplace(0.0, 1.0 / per_level)

    def recurse(cell: QuadCell, pts: np.ndarray) -> QuadCell:
        if cell.depth >= max_depth or observed(cell.count) < 4 * k:
            return cell

        kids, kid_pts = [], []
        for (a, b, c, d) in cell.quadrants():
            mask = ((pts[:, 0] >= a) & (pts[:, 0] < c) &
                    (pts[:, 1] >= b) & (pts[:, 1] < d))
            kid_pts.append(pts[mask])
            kids.append(QuadCell(a, b, c, d, cell.depth + 1, int(mask.sum())))

        # Rollback: a geometric split does not respect a population floor, so
        # a cell above 4k can still produce a child below k. Keep the parent.
        if min(kid.count for kid in kids) < k:
            return cell

        cell.children = [recurse(kid, p) for kid, p in zip(kids, kid_pts)]
        return cell

    root = QuadCell(x0, y0, x1, y1, 0, len(points))
    return recurse(root, points)


def leaves(root: QuadCell) -> list[QuadCell]:
    out: list[QuadCell] = []
    stack = [root]
    while stack:
        c = stack.pop()
        (out if c.is_leaf else stack).extend([c] if c.is_leaf else c.children)
    return out

Verification # permalink

Every leaf clears the floor. The tree is meant to be safe by construction, so this assertion should never fire — which is exactly why it belongs in the test suite:

def check_tree(root: QuadCell, k: int, total: int) -> dict:
    lv = leaves(root)
    counts = np.array([c.count for c in lv])
    return {
        "leaves": len(lv),
        "min_count": int(counts.min()),
        "floor_holds": bool(counts.min() >= k),
        # The partition must be exact: every point in exactly one leaf.
        "mass_conserved": int(counts.sum()) == total,
        # No leaf should be a lone survivor among siblings — that shape means
        # a rollback was skipped and complementary subtraction is available.
        "max_depth_reached": max(c.depth for c in lv),
        "size_ratio": float(counts.max() / counts.min()),
    }

Mass is conserved. Half-open quadrant bounds (>= a, < c) are what make the partition exact; using <= on both sides double-counts points on internal boundaries, and the failure is invisible until someone sums the map and gets more residents than the city has.

The structure does not leak. Build the tree twice, once with a randomly chosen resident removed, and compare the geometries. Under an unnoised split rule, roughly one boundary in a few hundred will move — and a moved boundary is a one-bit inference about that resident. With epsilon_structure set, the geometries should differ at a rate consistent with the noise, not with the data:

def structure_leak_rate(points: np.ndarray, extent, k: int,
                        trials: int = 200, seed: int = 0, **kw) -> float:
    """Fraction of leave-one-out rebuilds whose geometry changes."""
    rng = np.random.default_rng(seed)
    base = {(c.x0, c.y0, c.x1, c.y1) for c in leaves(build_quadtree(points, extent, k, **kw))}
    changed = 0
    for _ in range(trials):
        drop = rng.integers(len(points))
        alt = np.delete(points, drop, axis=0)
        cells = {(c.x0, c.y0, c.x1, c.y1) for c in leaves(build_quadtree(alt, extent, k, **kw))}
        changed += (cells != base)
    return changed / trials

A rate near zero with unnoised splits does not mean the structure is safe — it means the test population was not near a threshold. Run it with the real data.

Edge Cases & Adjustments # permalink

• Root extent fitted to the data. A root cell computed as the bounding box of the points leaks the extremes: the north-east corner of the study area is a resident’s exact location, to within the rounding. Snap the root to a fixed administrative or projected-grid extent decided independently of the data.
• Comparability across releases. An adaptive grid rebuilt each period produces a different geometry each period, so time series are not directly comparable. Either fix the geometry from a reference period and re-count into it, or publish the geometry alongside each release and require consumers to re-aggregate to a common coarse grid.
• Very skewed populations. Where one cell holds 40 % of the population, the tree recurses deeply there and $D_{\max}$ binds rather than $k$. That is fine, but check whether the deepest cells are small enough to be sensitive on their own — a 30 m cell holding exactly $k$ people is a building.
• Points on cell boundaries. Use half-open intervals consistently and document which edges are inclusive. Data collected on a rounded coordinate grid will pile points exactly on boundaries, and inconsistent handling shows up as a visible seam.
• Combining with noise. The counts published for the leaves still need their own noise or their own suppression. An adaptive grid controls the minimum count, which is a k-anonymity property, not a differential-privacy one.

FAQ # permalink

Why $4k$ rather than $2k$ or $k$?

Because a split produces four children. At $2k$ most splits will be rolled back and the recursion wastes work; at $k$ every split is guaranteed to fail. $4k$ is the smallest threshold under which all four children can clear the floor.

Can I keep the children that clear the floor and suppress the rest?

No — that is the complementary suppression trap. The parent total minus the surviving children reveals the suppressed ones. Roll the whole split back.

Does the noised-split version still guarantee every leaf clears $k$?

Not by itself. The noised split decides whether to attempt a subdivision; the rollback check on true counts is what enforces the floor. If the rollback also uses noised counts, add a margin — check against $k + 3/\varepsilon_{\text{level}}$ rather than $k$.

How deep should $D_{\max}$ go?

Until a cell would be small enough to identify a building. Below roughly 50 m in a residential area, cell size itself becomes the disclosure regardless of count.

Related # permalink

• Grid Aggregation & Spatial Binning Strategies — uniform grids and when they are the right choice
• Setting Minimum Count Thresholds for Published Map Cells — choosing $k$
• Applying Complementary Suppression to Choropleth Maps — the arithmetic the rollback avoids
• Handling Outliers That Break Spatial K-Anonymity — what to do with the isolated points a quadtree cannot help
• Tuning RAPPOR-Style Encoding for Grid-Cell Reports — why the cell alphabet has a detection floor

← Back to Grid Aggregation & Spatial Binning Strategies