Spatial k-anonymity explained

Problem statement

"Anonymised" is not a measurable claim. k-anonymity is: a release is k-anonymous when every record is indistinguishable from at least k−1 others on the fields an attacker could join on. Applied to geometry, it becomes the only privacy statement you can write down and check — every released location is consistent with at least k possible subjects.

Two things make the spatial version harder than the tabular one:

• The candidate pool is not in your data. For a table, k is counted within the released rows. For a location, k is counted in the world: how many dwellings, people or businesses could that point be? That number comes from an address file or a population grid, and the answer depends on which you use.
• k varies wildly across a single dataset. In the Brighton & Hove address extract used here, the distance needed to reach five addresses, the point's own included, has a median of 19.3 m and a maximum of 1,303.6 m. One fixed radius cannot deliver one k.

This guide defines the spatial version precisely, shows how to compute it, and explains why a fixed masking radius gives you a distribution of k rather than a value.

Quick answer

Compute k as the number of candidate subjects within the uncertainty area of each released point, and report the minimum, not the mean:

import numpy as np
from scipy.spatial import cKDTree

tree = cKDTree(np.c_[addresses.geometry.x, addresses.geometry.y])
released = np.c_[out.geometry.x, out.geometry.y]

k = np.array([len(tree.query_ball_point(p, RADIUS)) for p in released])
print(f"k: min {k.min()}, median {np.median(k):.0f}, "
      f"points below k=5: {(k < 5).sum()} ({(k < 5).mean():.2%})")

k: min 1, median 113, points below k=5: 113 (2.78%)

A release is k-anonymous at k=5 when k.min() >= 5. If even one point falls below, the release is not — the failing points are exactly the isolated ones, and they are exactly the ones an attacker looks at first.

Choose the candidate population and an honest uncertainty area

1. Choose the population that counts as a candidate

k is a count of plausible subjects, so the denominator has to match the dataset. For health cases it is dwellings or residents; for business records it is business premises; for wildlife it is potential habitat, not houses. Using total population where the subject must be a household inflates k by the household size and overstates the protection.

2. Pick the uncertainty area honestly

The area is whatever a knowledgeable attacker can rule out. For a rounded coordinate it is the rounding cell. For a donut mask with radius range [rmin, rmax] it is the annulus — and crucially, if the attacker knows the parameters, points inside rmin are excluded, which shrinks the candidate set relative to a plain disc. For aggregation it is the polygon. Report the shape you used.

3. Compute the distribution, not a summary

The headline number is the minimum. The useful number is the share below the threshold, because that tells you how much data you must move or drop.

4. Fix the failures adaptively

The isolated points are the problem, so give them a bigger radius rather than enlarging everyone's. An adaptive mask sizes each point's displacement from its own kth-nearest-neighbour distance, which equalises k and keeps dense areas accurate. On the Brighton addresses:

The maxima are the rural-edge points, and they are where a fixed 300 m radius would have failed.

5. Decide what happens to the points that cannot reach k

Some points cannot reach k at any acceptable radius — a farmhouse with no neighbours for a kilometre. The options are: drop them, snap them to a coarser unit (the settlement, the ward), or generalise the attribute instead of the geometry. Silently displacing them by 3 km is the worst of the three because it looks like data.

6. Say which auxiliary dataset produced k

k computed against an incomplete address file is optimistic in coverage terms and pessimistic in count terms. The Brighton extract holds 4,059 OpenStreetMap address nodes for a city of about 277,000 people at the 2021 Census, so its k values are a small fraction of what a complete national address file would give. State the source, the date and the coverage in the metadata alongside k.

Fixed and adaptive radii measured as k

The data used on this page

Every OpenStreetMap node in Brighton & Hove carrying an addr:housenumber, in British National Grid metres. The same extract is both the released points and the candidate pool, so k here counts addresses in the extract, the point's own included; out is the extract donut-masked by 50–300 m, and RADIUS is 300 m. Overpass via the maps.mail.ru mirror.

import geopandas as gpd
import numpy as np
import osmnx as ox
from scipy.spatial import cKDTree

ox.settings.overpass_url = "https://maps.mail.ru/osm/tools/overpass/api"
ox.settings.overpass_rate_limit = False
ox.settings.http_user_agent = "spatialworkflow.io guide examples (https://www.spatialworkflow.io/)"
area = ox.geocode_to_gdf("Brighton and Hove, England").geometry.iloc[0]
features = ox.features_from_polygon(area, tags={"addr:housenumber": True})
addresses = features[features.index.get_level_values(0) == "node"][["geometry"]].reset_index(drop=True).to_crs(27700)
released_xy = candidates_xy = np.c_[addresses.geometry.x, addresses.geometry.y]

rng0 = np.random.default_rng(1)
theta = rng0.uniform(0, 2 * np.pi, len(released_xy))
r = np.sqrt(rng0.uniform(0, 1, len(released_xy)) * (300**2 - 50**2) + 50**2)
out = gpd.GeoDataFrame(geometry=gpd.points_from_xy(released_xy[:, 0] + r * np.cos(theta),
                                                   released_xy[:, 1] + r * np.sin(theta)), crs=27700)
RADIUS = 300
print(f"{len(addresses):,} address points")

4,059 address points

Example 1 — k for a fixed masking radius

import numpy as np
from scipy.spatial import cKDTree

tree = cKDTree(candidates_xy)          # dwellings, businesses, whatever the subject is

for radius in (100, 250, 500, 1000):
    k = np.array([len(tree.query_ball_point(p, radius)) for p in released_xy])
    print(f"{radius:5d} m: k min {k.min():4d}  median {np.median(k):6.0f}  "
          f"below 5: {(k < 5).sum():4d}  below 10: {(k < 10).sum():4d}")

  100 m: k min    1  median     35  below 5:  389  below 10:  697
  250 m: k min    1  median    113  below 5:  106  below 10:  275
  500 m: k min    1  median    277  below 5:   22  below 10:   68
 1000 m: k min    2  median    673  below 5:    2  below 10:   12

Example 2 — an adaptive radius that targets a k

import numpy as np
from scipy.spatial import cKDTree

def adaptive_radius(points_xy, candidates_xy, k=5):
    """Distance from each point to the kth nearest candidate subject."""
    tree = cKDTree(candidates_xy)
    d, _ = tree.query(points_xy, k=k)
    return d[:, -1]

r = adaptive_radius(released_xy, candidates_xy, k=5)
print(f"radius: median {np.median(r):.1f} m, 95th pct {np.percentile(r, 95):.1f} m, "
      f"max {r.max():.1f} m")
print(f"points needing more than 500 m to reach k=5: {(r > 500).sum()}")

radius: median 19.3 m, 95th pct 162.8 m, max 1303.6 m
points needing more than 500 m to reach k=5: 22

22 of 4,059 points needed more than 500 m — the farms and houses on the Downs inside the city boundary. Those 22 are the release's real privacy decision; everything else is routine.

Example 3 — masking inside the adaptive radius

rng = np.random.default_rng(20260915)

def mask_to_k(points_xy, radius):
    theta = rng.uniform(0, 2 * np.pi, len(points_xy))
    r = np.sqrt(rng.uniform(0, 1, len(points_xy))) * radius     # uniform over the disc
    return points_xy + np.c_[r * np.cos(theta), r * np.sin(theta)]

masked = mask_to_k(released_xy, adaptive_radius(released_xy, candidates_xy, k=10))
displacement = np.hypot(*(masked - released_xy).T)
print(f"displacement: median {np.median(displacement):.1f} m, "
      f"max {displacement.max():.1f} m")

displacement: median 23.6 m, max 1271.1 m

Example 4 — the target-k table and the fixed radii

for target in (5, 10, 25):
    r = adaptive_radius(released_xy, candidates_xy, k=target)
    d = np.hypot(*(mask_to_k(released_xy, r) - released_xy).T)
    print(f"k={target:2d}: radius median {np.median(r):.1f} m, max {r.max():.1f} m; "
          f"displacement median {np.median(d):.1f} m")
tree = cKDTree(candidates_xy)
for radius in (100, 300, 500):
    k = np.array([len(tree.query_ball_point(p, radius)) for p in released_xy])
    print(f"fixed {radius} m: {(k < 5).sum()} points below k=5")

k= 5: radius median 19.3 m, max 1303.6 m; displacement median 13.1 m
k=10: radius median 33.9 m, max 1415.4 m; displacement median 23.6 m
k=25: radius median 74.2 m, max 1636.0 m; displacement median 50.7 m
fixed 100 m: 389 points below k=5
fixed 300 m: 85 points below k=5
fixed 500 m: 22 points below k=5

Note the square root inside the radius draw. Without it, points bunch towards the centre of the disc and the effective k is lower than intended.

Why k-anonymity is necessary but not sufficient

Why k-anonymity and not a probability

A probability of re-identification needs a model of the attacker; k needs an address file. k is also compositional in a way probabilities are not: if every point has at least k candidates, the whole release does, and that statement survives being quoted in a data-sharing agreement.

Why the annulus makes things worse, not better

A donut mask's inner radius exists to stop a point landing on itself. If the parameters are published — and they should be — the attacker also knows the true location is not within rmin, so the candidate set excludes the dwellings nearest the released point. In sparse areas that can remove the only plausible candidates and leave a smaller pool than a plain disc would.

Why k-anonymity is necessary but not sufficient

Two failures survive it. Homogeneity: if all k candidates share the sensitive attribute, knowing which one is irrelevant — that is what ℓ-diversity addresses. Composition: two k-anonymous releases of the same people can intersect to something that is not. The second is the reason repeat releases need a stored mask or a noise budget rather than a fresh draw.

Why the choice of candidate layer changes everything

k is a ratio between your points and someone else's. A population grid at 1 km resolution will hand you a k in the thousands for any radius; an address file will hand you tens. Neither is wrong, but only one matches an attack that works address by address. Use the finest candidate layer that represents a real subject.

Conventions, minimums and clustered subjects

• k=5 is a convention, not a law. Statistical agencies use 3, 5, 10 and 25 for different sensitivities.
• Report the minimum, always. A mean k of 400 with a minimum of 1 is a failed release.
• Clusters of subjects break the count. A block of forty flats is forty candidates at one coordinate only if the attacker cannot tell them apart.
• Time slices reduce k. k computed on the whole dataset is not k for the subset a user can filter to.
• Moving the point does not change k if the area does not. Displacement without an uncertainty claim is theatre.
• Rural points dominate the cost. Reaching k=5 everywhere usually means a handful of points move kilometres.
• k is not additive across releases. Two k=5 releases of the same people can compose to k=1.
• Publish k, not the radius. The radius is an implementation detail; k is the claim.

Internal links

• Re-identification risk in spatial data explained — the attack k is defending against
• Geoprivacy explained: why coordinates are personal data — why the geometry is the quasi-identifier
• Geomasking methods explained: donut, random and adaptive — how the adaptive radius is applied
• How to measure re-identification risk in a point dataset — computing k as an audit step
• Aggregation and suppression rules explained — the k threshold applied to counts instead of points
• How to aggregate points to units that meet a minimum count — reaching k by changing the geometry
• How to find the nearest point in GeoPandas — the neighbour search k is built on
• Anonymised points still identify individuals — what happens when only the mean k is checked

FAQ

What is spatial k-anonymity?

A release is spatially k-anonymous when every released location is consistent with at least k plausible subjects — dwellings, people or premises — given the uncertainty the release admits to.

What value of k should I use?

Five is the common floor for statistical releases and ten or more for sensitive health data. The value should come from the harm of being identified, not from what the data can bear.

Should I report the mean or the minimum k?

The minimum. An attacker will find the isolated points, and a high mean tells you nothing about them.

Why does a fixed masking radius fail?

Because candidate density varies. In the Brighton test, reaching k=5 needed 19.3 m in the median case and 1,303.6 m at the extreme — a 68-fold range within one city.

Does k-anonymity protect against everything?

No. If every candidate shares the sensitive attribute, k does not help, and two k-anonymous releases can intersect to identify someone.

Which layer should I count candidates in?

The one that represents a possible subject: an address file for households, a premises register for businesses. A coarse population grid inflates k without adding protection.