Sector-Specific k-Anonymity Thresholds for Location Data

There is no universal k: de-identified health data leans on the $k \ge 11$ precedent behind HHS Expert Determination, official statistics enforce a rule-of-3 or rule-of-5 cell-suppression floor, and public mobility releases push to $k \ge 100$ or higher because trajectory uniqueness dwarfs point uniqueness — the correct threshold is the one your sector’s regulators and peer releases already treat as defensible.

Picking a number in isolation is how releases fail audit. A reviewer will not accept “we used k=5 because it seemed reasonable”; they will ask which precedent, which quasi-identifiers, and which residual-risk figure that number encodes. This guide ties each sector’s k to the re-identification bound it is meant to satisfy, part of the broader compliance mapping for GDPR/CCPA location data.

The diagram below shows why a single number cannot serve every release: the same anonymity-set size maps to a very different disclosure risk depending on how many points an adversary can chain together, which is what separates a clinic visit from a commute.

Core Calculation # permalink

k-anonymity guarantees that every combination of quasi-identifier values is shared by at least $k$ records. Against those quasi-identifiers, the probability an adversary correctly singles out a target is bounded by the inverse group size:

So $k = 11$ caps identity disclosure at $9.09\%$, $k = 5$ at $20\%$, and $k = 100$ at $1\%$. The threshold a sector chooses is a direct statement of the disclosure risk it will tolerate.

The reason mobility needs a larger k is that uniqueness compounds along a trajectory. If each of $m$ visited locations independently places a person in a group of size $k$, the expected number of others sharing the entire sequence collapses roughly as:

for a population $N$. Two or three points is often enough to drive that expectation below 1 — the empirical result behind estimating uniqueness of mobility traces — which is why a per-point $k$ that is comfortable for a clinic visit is unsafe for a trip.

Sector threshold table # permalink

The audience matters as much as the sector: the same OD matrix might use $k \ge 5$ inside a secure enclave and $k \ge 100$ for open publication. The enclave lowers the floor because a data-use agreement, authenticated access, and query logging shrink the realistic adversary — a motivated intruder outside the building is replaced by a vetted analyst who can be audited and sanctioned. Strip those controls away and the same data needs a much larger crowd to be safe.

Three forces set where a sector’s number lands. The sensitivity of the payload raises it: health status, immigration status, or reproductive-care locations justify a higher k than a bus tap. The dimensionality of the release raises it: every extra quasi-identifier column — a fare type, an age band, an hour bucket — multiplies the number of groups and shrinks each one, so richer releases need either a bigger k or coarser keys. And the repetition of release raises it: a monthly feed from the same source gives an adversary successive views to intersect, so a k that is safe once is not safe published twelve times without fresh suppression.

Worked numeric example # permalink

A transit agency publishes tap-in counts per (stop, 15-minute window). One quasi-identifier group — stop S-142, window 07:30, fare-type senior — contains 3 riders. Under a rule-of-5 policy chosen for public release:

That exceeds the $20\%$ ceiling the rule-of-5 encodes, so the cell is suppressed or merged with the adjacent window until $k \ge 5$. Merging 07:30 and 07:45 yields 8 riders, restoring $\Pr[\text{re-identify}] \le 12.5\%$.

Python Implementation # permalink

Given a dataset and a sector, this function selects k from a policy map, groups by the declared quasi-identifier, and reports every group that fails — the same grouping logic detailed in calculating k-anonymity thresholds for mobile tracking. Coordinates are assumed pre-binned to a grid in EPSG:4326.

from __future__ import annotations

from dataclasses import dataclass, field

import pandas as pd

# Sector -> minimum k. These encode published regulatory precedent, not
# preference: k>=11 tracks the HHS Expert Determination guidance for health,
# rule-of-5 the statistical-office cell-suppression floor, k>=100 the
# trajectory-uniqueness result for public mobility releases.
SECTOR_K = {
    "health": 11,
    "official_statistics": 5,
    "mobility_public": 100,
    "transit": 5,
    "restricted": 3,
}


@dataclass
class KAnonymityReport:
    """Result of a sector-calibrated k-anonymity check."""

    sector: str
    k: int
    quasi_identifiers: list[str]
    n_groups: int
    failing_groups: pd.DataFrame  # groups with size < k
    min_group_size: int
    passes: bool = field(init=False)

    def __post_init__(self) -> None:
        self.passes = self.failing_groups.empty


def check_sector_k_anonymity(
    df: pd.DataFrame,
    sector: str,
    quasi_identifiers: list[str],
) -> KAnonymityReport:
    """Verify a location dataset meets its sector's k-anonymity floor.

    Args:
        df: One row per released record. Spatial quasi-identifiers (grid cell,
            tract, stop id) must already be generalized to the release unit.
        sector: Key into SECTOR_K selecting the regulatory threshold.
        quasi_identifiers: Columns an adversary could join on — spatial unit
            plus any temporal or attribute keys (hour bucket, fare type, etc.).

    Returns:
        A KAnonymityReport listing every group whose size is below k.

    Raises:
        KeyError: If the sector has no defined threshold, so no silent default.
    """
    if sector not in SECTOR_K:
        raise KeyError(f"No k-anonymity policy for sector {sector!r}.")

    k = SECTOR_K[sector]

    # Group size against the *declared* quasi-identifiers is the anonymity set.
    sizes = (
        df.groupby(quasi_identifiers, observed=True)
        .size()
        .rename("group_size")
        .reset_index()
    )

    # A group failing k must be suppressed, merged, or generalized before
    # release; we surface them rather than dropping silently.
    failing = sizes[sizes["group_size"] < k].sort_values("group_size")

    return KAnonymityReport(
        sector=sector,
        k=k,
        quasi_identifiers=quasi_identifiers,
        n_groups=len(sizes),
        failing_groups=failing,
        min_group_size=int(sizes["group_size"].min()) if len(sizes) else 0,
    )

Verification # permalink

The report is the audit artifact; assert on it before any release:

report = check_sector_k_anonymity(
    trips_df, sector="mobility_public",
    quasi_identifiers=["grid_cell", "hour_bucket"],
)

# Gate the release on the sector floor.
assert report.passes, (
    f"{len(report.failing_groups)} groups below k={report.k}; "
    f"smallest is {report.min_group_size}. Suppress or generalize."
)

print(f"Sector={report.sector} k>={report.k} enforced across "
      f"{report.n_groups} groups; min group size {report.min_group_size}.")

The checklist an auditor should be able to tick:

• The chosen k matches a documented sector precedent, not an arbitrary pick.
• The quasi-identifier list includes every joinable column, spatial and temporal.
• Every group meets k, or is recorded as suppressed/merged with a count.
• The residual risk $1/k$ is stated numerically in the release notes.

Edge Cases & Adjustments # permalink

• Sparse regions dominate suppression: rural cells and off-peak windows fail k far more often than dense urban ones. Prefer adaptive spatial units — merge sparse cells upward — over a global fine grid that suppresses most of the map.
• Homogeneity (attribute disclosure): a group of $k \ge 100$ still leaks if all members share a sensitive attribute. Layer l-diversity or t-closeness on top of the count check when the payload is sensitive.
• Temporal quasi-identifiers: adding an hour bucket multiplies the group count and shrinks each group. Coarsen time before space when both push groups below k.
• Trajectories break point-level k: no per-point k protects a full trace. For sequences, move to trajectory-specific methods and re-run a full re-identification risk assessment for geospatial datasets rather than trusting a single-point threshold.

FAQ # permalink

Why do mobility datasets need a much larger k than health datasets?

Health de-identification typically protects one point per person against a bounded quasi-identifier set, where $k \ge 11$ caps re-identification near 9%. Mobility data is a sequence, and uniqueness rises steeply with trajectory length, so even large single-point groups can be unique across a whole trip. Public mobility releases therefore use $k \ge 100$ or shift to trajectory-level anonymization.

What is the rule of 3 or rule of 5 in official statistics?

National statistical offices suppress or aggregate any table cell whose count is below a fixed threshold — usually 3 or 5. It is k-anonymity as cell suppression: a geographic cell must represent at least k people before its count is published, otherwise it is rounded, merged with a neighbor, or blanked.

Does meeting a k threshold make a release compliant on its own?

No. k-anonymity bounds identity disclosure against the declared quasi-identifiers only. It does not prevent attribute disclosure in homogeneous groups and it weakens under linkage and repeated release. Treat the sector k as a floor, then add perturbation or differential privacy and re-assess.

Related

• Compliance Mapping for GDPR/CCPA Location Data — regulatory context for these thresholds
• Calculating k-Anonymity Thresholds for Mobile Tracking — the grouping mechanics behind these checks
• k-Anonymity Grouping for Location Traces — implementing anonymity sets on spatial data
• Re-identification Risk Assessment for Geospatial Datasets — validating residual risk beyond a single k
• De-identifying HIPAA Geotagged Health Records — where the k ≥ 11 health precedent is applied

← Back to Compliance Mapping for GDPR/CCPA Location Data