Spatial K-Anonymity for Health Microdata

Part of the Privacy-Preserving Spatial Analytics section, this guide shows how to make every released health record spatially indistinguishable from at least $k-1$ others against a real population-at-risk denominator, then hold that guarantee under audit. Spatial k-anonymity is the disclosure-control property that keeps a case map from re-identifying a patient through the sheer sparseness of the place they live, and it is the pivot on which almost every downstream release decision in a surveillance program turns.

The property sounds like ordinary tabular k-anonymity, but the denominator is different and that difference is the whole subject. In a table, a record is $k$-anonymous when its quasi-identifier tuple is shared by at least $k$ rows in the release. In space, the anonymity set is not “other released records” — it is the population at risk that occupies the same generalized geography. A census block with one reported case but four thousand residents is safe; a census block with one reported case and eleven residents is a near-certain re-identification regardless of how many other cases appear elsewhere in the file. Getting this denominator right is what separates a defensible spatial release from one that merely looks aggregated.

Concept & Epidemiological Alignment

Formally, let a released record be assigned to a generalized areal unit $u$ drawn from a partition of the study region. Let $P_c$ be the population-at-risk in an atomic population cell $c$ (a census block, a dasymetric grid cell, or a modeled residential surface). The achieved k of unit $u$ is the population that shares that geography:

$$k_u = \sum_{c \,\in\, u} P_c$$

A release satisfies spatial k-anonymity at level $k_{\min}$ when every unit that carries at least one released record clears the threshold:

$$k_u \ge k_{\min} \quad \forall\, u : n_u \ge 1$$

where $n_u$ is the case count assigned to $u$. The contrast with tabular k-anonymity is precise. Tabular k counts records that look alike; spatial k counts people who could plausibly be the record’s subject. Two records in the same block are not each other’s anonymity set — the residents of the block are. This is why a file can be tabularly k-anonymous on ZIP-code and age and still be spatially disclosive: the ZIP centroid may sit in a hamlet of forty people.

The population-at-risk denominator must match the case definition, not just total population. If you are releasing pediatric asthma admissions, the anonymity set is the child population of the unit, not everyone in it. Using resident totals where the at-risk group is a small stratum overstates $k_u$ and quietly under-protects the release. The same logic that drives a rate’s denominator drives its privacy denominator; they should be the same layer.

Spatial k-anonymity does not stand alone; it is the measurement layer that other privacy methods aim at. Geographic masking techniques perturb point locations to raise the effective anonymity set, but a mask is only trustworthy once its achieved $k$ has been measured against a population basis — displacement without a denominator is theater. Likewise, dasymetric population suppression removes cells whose case counts are too small to publish; k-anonymity supplies the population-side test that tells suppression which cells are genuinely re-identifying rather than merely low-count. The three methods share one currency: a defensible count of who lives where.

Method-Selection Table

There are two structurally different ways to reach $k_{\min}$, and the choice is driven by what you are releasing and how much geographic resolution downstream users need.

Adaptive areal aggregation is the workhorse for count data because it is exhaustive: every unit ends up in exactly one released region, so no resident silently disappears. Spatial generalization suits point releases where you want to keep resolution wherever the population supports it. Rare-disease cells almost always need the joint constraint — a region can clear a population threshold and still expose a single case, so the case count is a separate gate.

Spatial Data Prerequisites

Achieved-$k$ measurement is only as trustworthy as the population layer under it, so the prerequisites are strict. Every layer — cases, population, and any ancillary surface — must share one projected CRS chosen for area fidelity; population summed across a distorted projection is a distorted denominator. Follow the canonical coordinate reference systems for public health guidance and reproject before any spatial join or area computation. For U.S. national work, EPSG:5070 (CONUS Albers Equal Area) keeps block populations comparable across the map.

Minimum state before the pipeline runs:

• Population basis at finer resolution than the release units — census blocks or a modeled residential grid — carrying the at-risk count that matches the case definition, not just total residents.
• Stable unit identifiers (GEOID or equivalent) on both cases and units, so joins are deterministic and merge order is reproducible.
• Valid, single-typed geometries with no slivers; a fractured boundary reads as a missing adjacency and blocks a legitimate merge.
• A declared $k_{\min}$ and, for rare disease, a minimum case count, both drawn from written policy rather than convenience.

# Deterministic join of case counts to a population basis, with achieved-k per unit.
# Pinned: geopandas==0.14.4, pyproj==3.6.1, numpy==1.26.4
import logging
import numpy as np
import geopandas as gpd

logging.basicConfig(level=logging.INFO, format="%(asctime)s %(levelname)s %(message)s")
log = logging.getLogger("spatial_k")

EQUAL_AREA = "EPSG:5070"  # CONUS Albers — area-faithful denominators

def build_units_with_k(units_path, pop_path, geoid="geoid",
                       pop_field="pop_at_risk", case_field="cases"):
    """Return release units carrying achieved k (population at risk) and case counts."""
    units = gpd.read_file(units_path)
    pop = gpd.read_file(pop_path)
    for name, gdf in (("units", units), ("population", pop)):
        if gdf.crs is None:
            raise ValueError(f"{name} layer has no CRS; refuse to guess a denominator.")
    units = units.to_crs(EQUAL_AREA)
    pop = pop.to_crs(EQUAL_AREA)

    # Population cells are assigned to the unit that contains their representative point,
    # so every person is counted once (exhaustive, non-overlapping).
    pop["geometry"] = pop.representative_point()
    joined = gpd.sjoin(pop, units[[geoid, "geometry"]], predicate="within", how="inner")
    k_by_unit = joined.groupby(geoid)[pop_field].sum()

    units = units.set_index(geoid)
    units["achieved_k"] = k_by_unit.reindex(units.index).fillna(0.0)
    if case_field not in units.columns:
        units[case_field] = 0
    units = units.sort_index().reset_index()  # stable order => reproducible merges
    log.info("units=%d min_k=%.0f median_k=%.0f",
             len(units), units["achieved_k"].min(), units["achieved_k"].median())
    return units

Production Implementation: Adaptive Areal Aggregation

The core operation is a greedy contiguity merge: repeatedly take the unit with the lowest achieved $k$ that still violates the threshold, fold it into the neighbor that best absorbs it, recompute, and continue until no violating unit remains. Contiguity comes from a spatial weights object; building it correctly is its own discipline, covered in spatial weights matrix construction. The merge target should be the lowest-k eligible neighbor, which pulls two weak units together rather than diluting a healthy one, and ties must break on the stable identifier so the result is deterministic.

# Greedy contiguity merge to enforce spatial k-anonymity on areal counts.
# Pinned: geopandas==0.14.4, libpysal==4.12.1, numpy==1.26.4
import logging
import numpy as np
import geopandas as gpd
from libpysal.weights import Queen

log = logging.getLogger("spatial_k.merge")

def enforce_k_anonymity(units, k_min, geoid="geoid",
                        k_field="achieved_k", case_field="cases", min_cases=0):
    """
    Merge sub-threshold units into contiguous neighbors until every unit with at
    least one case satisfies achieved_k >= k_min (and cases >= min_cases if set).
    Returns (regions_gdf, merge_log). Deterministic: ties break on stable geoid.
    """
    units = units.sort_values(geoid).reset_index(drop=True)
    # region label per unit; merged units share a label
    units["region"] = units[geoid].astype(str)
    merge_log = []

    def region_frame():
        agg = units.dissolve(
            by="region",
            aggfunc={k_field: "sum", case_field: "sum"},
        )
        return agg

    while True:
        regions = region_frame()
        violating = regions[
            (regions[case_field] >= 1)
            & ((regions[k_field] < k_min) | (regions[case_field] < min_cases))
        ]
        if violating.empty:
            break
        # weakest region first — lowest population at risk, ties by label
        target = violating.sort_values([k_field, case_field]).index[0]

        # rebuild contiguity on current regions and find eligible neighbors
        w = Queen.from_dataframe(regions.reset_index(), ids=list(regions.index))
        neighbors = w.neighbors.get(target, [])
        if not neighbors:
            log.warning("region %s has no contiguous neighbor; flag for manual review", target)
            merge_log.append({"region": str(target), "action": "isolated_no_merge"})
            # remove from consideration by marking it suppressed downstream
            units.loc[units["region"] == target, "region"] = f"__suppressed__{target}"
            continue
        # merge into the neighbor with the smallest achieved k (join two weak units)
        best = min(sorted(neighbors), key=lambda n: (regions.loc[n, k_field], str(n)))
        units.loc[units["region"] == target, "region"] = str(best)
        merge_log.append({
            "from": str(target), "into": str(best),
            "k_after": float(regions.loc[best, k_field] + regions.loc[target, k_field]),
        })
        log.info("merged region %s into %s", target, best)

    regions = region_frame().reset_index()
    log.info("aggregation complete: regions=%d min_k=%.0f suppressed=%d",
             len(regions), regions[k_field].min(),
             units["region"].str.startswith("__suppressed__").sum())
    return regions, merge_log

The loop is intentionally naive about performance and strict about correctness: it recomputes contiguity each iteration so a freshly merged region’s adjacency is always current, and it never imputes. A unit that cannot reach a neighbor — an island, or a hole left by upstream suppression — is flagged rather than silently attached to a distant region, because attaching non-contiguous units would fabricate a geography that does not exist on the ground.

Parameter Selection & Tuning

Two parameters dominate the outcome, and both must be justified in writing rather than defaulted.

Choice of $k_{\min}$. The threshold encodes your tolerance for re-identification risk. Common statistical-agency practice sits at $k = 5$ for general small-area releases and rises to $k = 11$ or higher for sensitive conditions, reflecting the intuition that a larger anonymity set is harder to unwind with an external register. Higher $k$ means coarser maps; the sensitivity of the condition, not the convenience of the analyst, should set it. Run the aggregation across $k \in \{5, 11, 25\}$ and report how many units survive at native resolution under each — that curve is the honest cost statement for a coarser threshold.

Population source. The denominator can be decennial census blocks, annual small-area estimates, or a dasymetric residential surface. Each choice moves $k_u$. Census blocks are authoritative but age between counts; a block that housed four thousand people in 2020 may be a demolished lot today, which understates real population and over-suppresses. Model-based estimates are current but carry their own error, which can overstate $k$ and under-protect. Whatever you pick, pin its vintage in the audit record, because two runs on different population vintages are not comparable and a reviewer must know which denominator produced the release.

A useful diagnostic is the achieved-$k$ distribution before and after aggregation. If many units trail off below $k < 20$ before merging, expect heavy aggregation and a coarse map; if only a handful violate, the release keeps most of its resolution.

# Disclosure-risk summary before releasing.
# Pinned: numpy==1.26.4
import numpy as np

def disclosure_risk_report(regions, k_min, k_field="achieved_k", case_field="cases"):
    carrying = regions[regions[case_field] >= 1]
    k = carrying[k_field].to_numpy(float)
    report = {
        "regions_with_cases": int(len(carrying)),
        "min_achieved_k": float(np.min(k)) if k.size else None,
        "violations": int(np.sum(k < k_min)),          # must be zero to release
        "p05_achieved_k": float(np.percentile(k, 5)) if k.size else None,
        "unique_case_regions": int(np.sum(carrying[case_field] == 1)),
    }
    assert report["violations"] == 0, "k-anonymity violated; do not release"
    return report

Edge Cases & Failure Modes

• Rural sparsity. In frontier counties, a single unit can be below $k_{\min}$ even after several merges, producing a region the size of a small state. That is the correct behavior, not a bug: the alternative is disclosure. Report the maximum region area so downstream users understand the resolution they are actually getting.
• Rare disease. A region can clear a population threshold while still containing exactly one case, and a lone case in a well-populated region is still a potential re-identification if the condition is distinctive. This is why the case-count gate (min_cases) is independent of the population gate; the deep dive in adaptive areal aggregation for rare-disease counts treats the joint constraint in full.
• Boundary effects. Units at the edge of the study frame have fewer neighbors to merge with, so they aggregate into larger regions than interior units of the same density. Pad the population layer one ring beyond the reporting boundary so edge units have realistic neighbors, then clip released regions back to the reporting area only at output.
• Point releases in low density. Publishing a case point — even a jittered one — can violate k-anonymity where population thins out, because the disc that actually contains $k$ people may be far larger than the jitter radius. That failure and its fix are the subject of enforcing spatial k-anonymity on case-point releases.
• Stale population layer. A census-block denominator years past its count date can both over- and under-protect in different places; treat vintage as a first-class parameter, not a footnote.

Compliance & Audit Controls

A k-anonymized release is defensible only if a reviewer can reconstruct exactly how it was produced. The audit record for one run is small and non-negotiable: the $k_{\min}$ (and any minimum case count), the population layer identity and vintage, the CRS authority code, the full ordered merge log, the list of suppressed or isolated units, and pinned library versions. The merge log matters more than it looks — because the greedy algorithm is order-dependent, the sequence of merges is the method, and a run without it cannot be reproduced.

# Bind an audit record to every released artifact.
# Pinned: geopandas==0.14.4, pyproj==3.6.1
import hashlib, json, datetime as dt

def write_release(regions, merge_log, config, path):
    payload = {
        "k_min": config["k_min"],
        "min_cases": config.get("min_cases", 0),
        "population_source": config["population_source"],   # e.g. "census_block_2020"
        "crs_authority": regions.crs.to_authority()[1],
        "n_regions": int(len(regions)),
        "merge_events": merge_log,
        "generated_utc": dt.datetime.now(dt.timezone.utc).isoformat(),
    }
    payload["config_sha256"] = hashlib.sha256(
        json.dumps({k: payload[k] for k in ("k_min", "min_cases", "population_source")},
                   sort_keys=True).encode()
    ).hexdigest()
    regions.to_parquet(path, index=False, schema_metadata={
        "disclosure_control": json.dumps(payload),
    })
    return payload

Two governance rules close the loop. First, suppression and merging are release-blocking assertions, not warnings: disclosure_risk_report must show zero violations before an artifact is written, so a non-conforming region halts the pipeline instead of leaking. Second, the population vintage and $k_{\min}$ travel with the file, because a region map is meaningless — and potentially disclosive — if a later consumer reinterprets it against a different denominator.

Production Implementation Checklist

• All layers reprojected to one equal-area CRS before any population sum
• Population basis matches the case definition’s at-risk stratum, not just total residents
• Population vintage recorded in the audit block
• $k_{\min}$ (and minimum case count for rare disease) set from written policy
• Achieved $k$ computed by exhaustive, non-overlapping assignment of population cells
• Greedy merge deterministic; ties broken on stable identifier; merge order logged
• Non-contiguous / isolated units flagged for review, never attached to distant regions
• Boundary padding applied; regions clipped to reporting area at output only
• disclosure_risk_report shows zero violations as a release-blocking assertion
• Config hash, merge log, and population source embedded in the output artifact

Frequently Asked Questions

How is spatial k-anonymity different from ordinary k-anonymity? The anonymity set is the population at risk sharing the generalized geography, not the count of released records that look alike. A file can be tabularly k-anonymous on quasi-identifiers and still be spatially disclosive because a ZIP or block centroid lands in a tiny population.

What population should the denominator use? The at-risk stratum that matches the case definition. Releasing a childhood condition means the child population is the anonymity set; using total residents overstates achieved $k$ and under-protects the release.

What value of k should I choose? There is no universal number. Statistical agencies commonly use $k = 5$ for general small-area releases and raise it to $k = 11$ or more for sensitive conditions. Higher $k$ yields coarser maps, so set it from the sensitivity of the condition and report the resolution cost.

Why merge into the lowest-k neighbor instead of the largest? Folding a weak unit into another weak unit consolidates two problems into one solution and preserves resolution elsewhere. Merging into an already-large region wastes the neighbor’s capacity and coarsens the map faster than necessary.

Related Topics

• Geographic Masking Techniques — perturbs point locations; k-anonymity supplies the population test that certifies a mask.
• Dasymetric Population Suppression — the count-side control that pairs with the population-side test described here.
• Enforcing Spatial K-Anonymity on Case-Point Releases — the point-release variant where jitter alone is not enough.
• Adaptive Areal Aggregation for Rare-Disease Counts — the joint population-and-case-count constraint in depth.
• Spatial Weights Matrix Construction — the contiguity object the greedy merge depends on.