# Assessing Re-identification Risk in Point Datasets

Measure spatial k-anonymity — for each point, how many other points fall within the uncertainty radius a recipient could reasonably assume — and report the distribution rather than an average, because the datasets that cause harm are the ones with a long tail of isolated points in a mostly dense layer.

Point datasets about people are published constantly and assessed rarely, usually on the reasoning that the identifying columns were removed. That reasoning is incomplete: in a sparse area a single point at address resolution identifies a household as effectively as a name would. The measurement below turns that intuition into a number that can be compared, tracked and gated on. This guide sits under regulatory obligations for location data, within Spatial Data Audit Reporting & Compliance Governance.

# Automated Python Implementation

#!/usr/bin/env python3
"""Measure spatial k-anonymity across a point dataset."""
import geopandas as gpd
import numpy as np
from shapely.strtree import STRtree


def spatial_k(gdf, radius_m, metric_crs="EPSG:3857", group_by=None):
    """For each point, how many points (including itself) fall within radius_m."""
    if gdf.crs is None:
        raise ValueError("layer has no CRS; distances would be meaningless")
    projected = gdf.to_crs(metric_crs)

    def counts_for(frame):
        geoms = list(frame.geometry)
        tree = STRtree(geoms)
        out = np.empty(len(geoms), dtype=int)
        for i, geom in enumerate(geoms):
            candidates = tree.query(geom.buffer(radius_m))
            out[i] = sum(1 for j in candidates if geoms[j].distance(geom) <= radius_m)
        return out

    if group_by is None:
        projected["k"] = counts_for(projected)
    else:
        # Anonymity is only within the group a recipient can distinguish.
        projected["k"] = 0
        for _, index in projected.groupby(group_by).groups.items():
            subset = projected.loc[index]
            projected.loc[index, "k"] = counts_for(subset)
    return projected


def summarise(projected, threshold=5):
    k = projected["k"].to_numpy()
    return {
        "points": int(k.size),
        "min_k": int(k.min()),
        "median_k": float(np.median(k)),
        "p05_k": float(np.percentile(k, 5)),
        "below_threshold": int((k < threshold).sum()),
        "share_below": float((k < threshold).mean()),
        "threshold": threshold,
    }


def worst_offenders(projected, threshold=5, limit=20):
    """The specific points to fix, not just the count of them."""
    risky = projected[projected["k"] < threshold].sort_values("k")
    return risky.head(limit)[["k", "geometry"]]

Two decisions in this measurement carry most of its usefulness.

The radius represents recipient uncertainty, not a privacy parameter to be tuned until the number looks acceptable. If the points are published at 100 metre resolution, the recipient can locate each to within roughly that distance, so 100 metres is the radius. Choosing a larger radius because it yields a better k is measuring a different, more comfortable question.

Grouping matters when the attributes distinguish points. If each point carries a category — incident type, service class — then a recipient distinguishes points within a category, and anonymity has to be computed within it. Twenty points in a cell provide no protection to the only one of its type.

# Validation and Pipeline Integration

def test_isolated_point_has_k_of_one():
    gdf = gpd.GeoDataFrame(geometry=gpd.points_from_xy([0, 10], [0, 10]),
                           crs="EPSG:4326")
    result = spatial_k(gdf, radius_m=50)
    assert result["k"].min() == 1


def test_grouping_reduces_k():
    gdf = gpd.GeoDataFrame(
        {"kind": ["a", "b", "b", "b"]},
        geometry=gpd.points_from_xy([0, 0, 0, 0], [0, 0, 0, 0]),
        crs="EPSG:4326")
    assert spatial_k(gdf, 50)["k"].min() == 4
    assert spatial_k(gdf, 50, group_by="kind")["k"].min() == 1


def test_missing_crs_is_refused():
    gdf = gpd.GeoDataFrame(geometry=gpd.points_from_xy([0], [0]), crs=None)
    try:
        spatial_k(gdf, 50)
    except ValueError:
        return
    raise AssertionError("distances without a CRS must be refused")

Run the measurement as part of the publication assessment rather than as a gate on every commit. Report the distribution and the worst offenders into the assessment record described in regulatory obligations for location data, so a decision to publish is made against numbers rather than impressions.

# Suppression Bias, and Why It Is Not Free

Removing the low-k points is the obvious response and it is the one that most often damages the data without anyone noticing.

The points with low k are not a random sample. They are disproportionately rural, disproportionately in low-density neighbourhoods, and disproportionately in whatever category is rare. Suppressing them produces a dataset that systematically under-represents exactly those populations, and any analysis built on it will conclude that the phenomenon is an urban one. The privacy problem has been solved by introducing an analytical error that is invisible to the recipient.

Three responses handle this better.

Generalise everything rather than suppressing some. Rounding every point to a coarser resolution reduces detail uniformly, which is a loss the recipient can see and reason about. It also usually raises the minimum k substantially, because coarsening has the largest effect precisely where points are sparse.

Publish the suppression count and its geography. If suppression is used, stating that four hundred points were removed and which areas they came from lets an analyst weight for it. Silent suppression does not.

Consider an aggregate instead. Where the point representation cannot be made safe at any useful resolution, a count per zone is honest about what is being published, and is frequently as useful for the actual purpose as the points would have been.

The one option that should be rejected is jittering points by a random offset without recording the method. It looks like generalisation, it defeats naive re-identification, and it silently corrupts every distance and containment calculation an analyst performs — including the ones that decide which zone a point falls in.

# Cost at Catalogue Scale

The neighbour count is quadratic in the worst case and the naive implementation becomes unusable somewhere around a hundred thousand points, which is well within the size of an ordinary address-derived layer.

The spatial index carries most of the load: querying a buffered geometry against an R-tree reduces the candidate set from every point to the handful nearby, which makes the practical cost close to linear for evenly distributed data. Where it degrades is in dense clusters, since a buffer over a city centre returns thousands of candidates that all then need an exact distance test.

Two adjustments keep it tractable. Querying with the buffer’s bounding box first and applying the exact distance only to what it returns avoids constructing a buffer geometry per point, which dominates the runtime at scale. And where only the count below a threshold is needed rather than the full distribution, the per-point loop can stop as soon as the threshold is reached — for a layer where most points are in dense areas, that turns the expensive majority into a constant-time check and leaves the full count only for the sparse tail, which is the part that mattered anyway.

# Long-Term Compliance Best Practices

• Report the distribution, never a single number. An average k conceals the tail that constitutes the risk.
• Set the radius from the published resolution. It represents what a recipient can infer, not a parameter to tune.
• Compute within groups the attributes distinguish. Anonymity among points a recipient can tell apart is not anonymity.
• Re-measure after every join. Adding a column can split a group and collapse k without touching the geometry.
• Record the measurement, not just the conclusion. The numbers are what a later reviewer needs; the verdict alone is not reviewable.

# Related

• Regulatory Obligations for Location Data — where this measurement fits in the assessment
• Redacting Sensitive Locations Before Publication — deterministic displacement and generalisation
• Enforcing Coordinate Precision and CRS in CI — the precision rule that bounds the radius
• Aggregating Compliance Metrics Across a Dataset Inventory — reporting these measurements across a catalogue