Handling Outliers That Break Spatial K-Anonymity

In every real spatial dataset a handful of points have no $k-1$ neighbours within any tolerable distance: the isolated farmstead, the single dwelling on an industrial estate, the one traveller who visited a remote valley. Those points decide the whole release. Force them into a group and the group’s extent becomes useless; drop them and the map develops holes shaped exactly like the people it was meant to protect.

Core Calculation # permalink

An outlier is defined relative to the utility ceiling, not the data. Let $r_{\max}$ be the largest spatial generalisation the release can tolerate. A point $p$ is an outlier when its $(k-1)$-th nearest neighbour lies beyond it:

The isolation ratio measures how far outside it is, and drives the disposal:

Four disposals, each with a different cost:

The decision rule that keeps the release honest is to bound the total suppressed mass rather than to decide point by point:

If applying the isolation thresholds suppresses more than $\tau$, the parameters are wrong — $k$ is too high, $r_{\max}$ too tight, or the study area too broad — and the fix is upstream, not per point.

The bias suppression leaves is the reason for the cap. Outliers are not randomly distributed: they are rural, they are poor or very rich, they are the edges of the map. Suppressing 3 % of points suppresses close to 100 % of some communities, and a release with that property is not merely less useful — it is systematically less useful for exactly the populations least able to notice.

Worked numeric example # permalink

A health-service dataset, 84 200 patient locations, $k = 5$, $r_{\max} = 2000$ m.

Suppressed share is 0.17 %, comfortably under $\tau = 1$ %. But check where those 146 sit: if 130 of them fall in two rural districts holding 900 patients between them, the release has erased 14 % of those districts while erasing 0.02 % of the city. Report the suppression rate per administrative unit, not just globally — the global figure is the one that hides the problem.

Python Implementation # permalink

from __future__ import annotations

from dataclasses import dataclass

import numpy as np
from scipy.spatial import cKDTree


@dataclass(frozen=True)
class OutlierPolicy:
    k: int = 5
    r_max: float = 2000.0
    merge_ratio: float = 2.0
    generalise_ratio: float = 4.0
    max_suppressed_share: float = 0.01


def classify_outliers(points: np.ndarray, policy: OutlierPolicy) -> np.ndarray:
    """Label each point 'ok', 'merge', 'generalise' or 'suppress'.

    Distance to the (k-1)-th neighbour is the whole diagnosis: it says how
    much generalisation this point would need to reach a group of k, which is
    exactly the utility the release would have to give up for it.
    """
    tree = cKDTree(points)
    # k+1 because the query returns the point itself at distance zero.
    dists, _ = tree.query(points, k=policy.k)
    d_k = dists[:, -1]
    iota = d_k / policy.r_max

    labels = np.full(len(points), "ok", dtype=object)
    labels[iota > 1.0] = "merge"
    labels[iota > policy.merge_ratio] = "generalise"
    labels[iota > policy.generalise_ratio] = "suppress"
    return labels


def apply_policy(points: np.ndarray, unit_ids: np.ndarray,
                 policy: OutlierPolicy) -> dict:
    """Apply the disposals and refuse the release if the cap is breached.

    The global cap is necessary and not sufficient: outliers are rural, poor
    or remote, so a compliant global rate routinely hides a district that has
    lost a tenth of its records.
    """
    labels = classify_outliers(points, policy)
    suppressed = labels == "suppress"
    share = suppressed.mean()

    per_unit = {}
    for unit in np.unique(unit_ids):
        mask = unit_ids == unit
        per_unit[str(unit)] = float(suppressed[mask].mean())

    worst_unit = max(per_unit, key=per_unit.get) if per_unit else None
    return {
        "labels": labels,
        "suppressed_share": float(share),
        "per_unit_share": per_unit,
        "worst_unit": worst_unit,
        "worst_unit_share": per_unit.get(worst_unit, 0.0) if worst_unit else 0.0,
        "passes_global_cap": bool(share <= policy.max_suppressed_share),
        # A unit losing more than a tenth of its records is not a masked unit,
        # it is a missing one, and consumers will read the gap as zero demand.
        "passes_unit_cap": all(v <= 0.10 for v in per_unit.values()),
    }

Verification # permalink

The hole must not be readable. Suppression removes points, and if the release also publishes a total, the suppressed count is the difference. Confirm that either the totals are suppressed too, or the suppressed mass is itself noised:

def hole_recoverable(published_units: dict[str, int], total: int,
                     suppressed_units: set[str]) -> bool:
    """True when subtracting the published units from the total names the gap.

    Publishing a grand total alongside per-unit counts hands back exactly the
    mass that suppression removed — and if only one unit was suppressed, it
    hands back that unit's count exactly.
    """
    residual = total - sum(published_units.values())
    return len(suppressed_units) == 1 and residual > 0

The merge must not create a group whose extent is a disclosure. A group of five spread over 40 km is nominally 5-anonymous and practically identifies each member by their position within it:

def check_group_extents(groups: list[np.ndarray], r_max: float) -> list[dict]:
    """A k-anonymous group whose diameter exceeds r_max is k-anonymous in name."""
    out = []
    for i, g in enumerate(groups):
        diameter = float(np.linalg.norm(g[:, None] - g[None, :], axis=2).max())
        out.append({"group": i, "size": len(g), "diameter_m": diameter,
                    "usable": diameter <= r_max})
    return out

Re-run the classification after the disposals. Merging changes the neighbour structure, so a point that was fine before a merge can become an outlier after it. Iterate to a fixed point, and bound the iterations — if the classification has not stabilised in five passes, the parameters are unsatisfiable and $k$ or $r_{\max}$ has to move.

Compare the suppressed population’s attributes to the retained population’s. If the suppressed group is significantly older, poorer or more rural than the retained one, say so in the release notes. That statement is the difference between a limitation and a hidden defect.

Edge Cases & Adjustments # permalink

• Outliers created by the mask. Jittering or fuzzing can push a point out of a group and into isolation. Classify after the mask, not before, or the check validates a dataset that was never published.
• Temporal outliers. A point can be spatially crowded and temporally isolated — the only record in a district at 4 a.m. Apply the same $d_{k-1}$ logic in the time dimension and take the worse of the two.
• Repeat visitors. If one subject contributes many points, a “group of five” can be one person five times. Deduplicate by subject before counting neighbours; this is the single most common way a k-anonymity claim turns out to be false.
• Suppression as a signal to the subject. Someone who knows they live alone in a valley can infer from a published map that their record was suppressed — which tells them they are in the dataset. Where dataset membership is itself sensitive, suppression is not a sufficient disposal and generalisation to a very coarse unit is safer.
• The τ cap as a design tool. When the cap is breached, the useful response is usually to lower $k$ and add noise rather than to raise $r_{\max}$. Noise degrades everything slightly; generalisation degrades the rural map enormously.

FAQ # permalink

Isn’t suppressing 0.2 % of points obviously fine?

Globally, yes. Per district it can be 14 %, and the consumers who care about rural provision are the ones the release will mislead. Always report the per-unit rate.

Can I just raise $r_{\max}$ until nothing is an outlier?

You can, and the resulting groups will be tens of kilometres wide, which satisfies the formal definition and protects nobody — a group that large identifies its members by position. Check group diameters, not just group sizes.

Is synthesising neighbours ever acceptable?

Only when the release explicitly documents that synthetic records are present, and only when the synthetic count is published separately so an analyst can subtract it. Otherwise it silently changes counts, which is worse than a documented gap.

How do I know when to move $k$ instead of handling outliers?

When the suppression cap is breached, or when more than a few percent of points need any disposal at all. At that point the parameters, not the points, are the problem.

Related # permalink

• K-Anonymity Grouping for Location Traces — the grouping this handles the residue of
• Building Quadtree Adaptive Grids for Uneven Density — avoiding outliers by construction
• Applying Complementary Suppression to Choropleth Maps — closing the recoverable hole
• Writing Pytest Assertions for K-Anonymity Guarantees — making these checks blocking
• Re-identification Risk Assessment for Geospatial Datasets — where outliers dominate the risk figure

← Back to K-Anonymity Grouping for Location Traces