🧭 Concept Privacy & sensitive locations Spatial statistics Geoprivacy & Anonymisation · step 3 of 20 Updated

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 the fifth nearest other address has a median of 21.9 m and a maximum of 533.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%})")

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.

Two panels: a fixed radius over dense housing giving many candidates, and the same radius over sparse housing giving two.
The same radius is two different privacy guarantees; only the candidate count is comparable.

Step-by-step solution

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:

target k median radius max radius median displacement
5 21.9 m 533.6 m 15.0 m
10 33.8 m 748.3 m 23.6 m
25 68.9 m 879.7 m 46.2 m

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 3,109 OpenStreetMap address nodes for a city of roughly 290,000 people, 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.

Bars comparing points failing k=5 under fixed radii of 100, 300 and 500 metres against an adaptive radius.
An adaptive radius reaches the target everywhere; a fixed one either fails the edges or blurs the centre.

Code examples

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}")

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 21.9 m, 95th pct 182.6 m, max 533.6 m
points needing more than 500 m to reach k=5: 2

Two of 3,109 points needed more than 500 m. Those two 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 580.1 m

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.

Explanation

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.

Checklist of what a k-anonymity claim must state: the minimum k, the candidate layer and date, the uncertainty shape, the records that could not reach k, and why a bare radius is not a claim.
Four things to publish, and one that is not a privacy statement on its own.

Edge cases or notes

  • 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.

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 21.9 m in the median case and 533.6 m at the extreme — a 24-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.