l-Diversity & t-Closeness for Spatial Attributes

A grid cell holding a hundred visits satisfies any k floor you care to set, and discloses a diagnosis with certainty if all hundred visits were to the same oncology clinic. k-anonymity protects identity; l-diversity and t-closeness protect the attribute, and location data needs both because the cell’s contents are frequently more sensitive than the cell’s location.

Why the k Floor Is Not Enough # permalink

The k-anonymity condition asks how many records share a generalized location. It says nothing about what those records contain. An adversary who learns that a target’s record falls into cell $c$ has learned nothing new about identity — that was the point — but if every record in $c$ carries the same sensitive value, the adversary has learned the value anyway.

This is called attribute disclosure, and spatial data produces it more often than tabular data does, for a structural reason: land use is clustered. A cell over a hospital campus contains hospital visits. A cell over a single place of worship contains attendance at that faith. A cell over an industrial estate contains shift workers. Generalizing a coordinate into such a cell increases the anonymity set while leaving the attribute perfectly determined, and the k check reports success.

Two definitions address it. l-diversity requires that the sensitive attribute take at least $l$ “well represented” values inside every published cell. t-closeness goes further and requires that the attribute’s distribution inside the cell be within distance $t$ of its distribution across the whole release, which additionally blocks a skew attack where a cell is diverse but wildly unrepresentative.

Both are stricter than k and both cost coverage. That trade is the subject of this page.

Algorithmic Specification # permalink

l-diversity # permalink

For a published cell $c$ with sensitive attribute values $s_1, \dots, s_m$ occurring with counts $n_1, \dots, n_m$, the simplest form — distinct l-diversity — requires

This is weak, because one value can still dominate. Entropy l-diversity is the usable form:

A cell with 18 oncology and 2 others has distinct diversity 3 and entropy diversity below $\log 2$, which is the correct verdict.

t-closeness # permalink

Let $P$ be the attribute distribution inside cell $c$ and $Q$ the distribution across the whole release. The cell satisfies $t$-closeness when

For an unordered attribute — POI category, service type — $D$ is usually total variation distance,

For an ordered or numeric attribute — income band, dwell duration, severity — use the Earth Mover’s Distance, which charges more for moving mass between distant values than adjacent ones:

Using total variation on an ordered attribute treats “band 1 versus band 2” as exactly as disclosive as “band 1 versus band 9”, which is wrong in the direction that matters.

The spatial complication # permalink

Both definitions assume the global distribution $Q$ is the right reference. Over a city with genuinely different neighbourhoods, it is not: a cell in a hospital district will never look like the city-wide mix, and forcing it to would suppress the entire district. The practical adaptation is a local reference: compare each cell against the distribution of its surrounding region rather than the whole release.

where $\mathcal{N}(c)$ is a ring of neighbouring cells. This preserves the geography that makes the map useful while still catching a cell that stands out from its own surroundings — which is the cell an adversary would actually target.

Parameter reference # permalink

Prerequisites & Data Requirements # permalink

• A declared sensitive attribute. These tests need to know which column is sensitive. Applying them to every column at once produces a release with nothing in it.
• An attribute taxonomy with a stated order, or an explicit statement that there is none. The choice between total variation and Earth Mover’s Distance depends on it, and the two give materially different verdicts.
• A cell geometry that already satisfies k. Diversity is checked on published cells, so it runs after grid aggregation or k-anonymity grouping, never instead of them.
• Counts of distinct individuals per value. A single frequent visitor can manufacture apparent diversity in the row counts while the person-level distribution stays homogeneous.
• Python dependencies. pandas and numpy for the tabulation, scipy.stats for entropy and scipy.stats.wasserstein_distance for the Earth Mover’s Distance.

Step-by-Step Implementation # permalink

Step 1 — Tabulate the attribute distribution per cell, over people # permalink

import pandas as pd

def cell_attribute_table(df: pd.DataFrame) -> pd.DataFrame:
    """Distinct individuals per (cell, sensitive value). Row counts overstate
    diversity whenever one person contributes many records."""
    return (df.groupby(["cell_id", "sensitive"])["person_id"]
              .nunique()
              .rename("n")
              .reset_index())

Step 2 — Score entropy l-diversity # permalink

import numpy as np

def entropy_diversity(counts: np.ndarray) -> float:
    """Effective number of well-represented values in one cell."""
    p = counts / counts.sum()
    p = p[p > 0]
    return float(np.exp(-(p * np.log(p)).sum()))     # exp(H) = effective count

Reporting $e^{H}$ rather than $H$ makes the threshold readable: an effective count of 1.4 for a supposed $l = 3$ is obviously failing, where an entropy of 0.34 nats is not.

Step 3 — Score closeness against a local reference # permalink

from scipy.stats import wasserstein_distance

def closeness(p: np.ndarray, q: np.ndarray, ordered: bool) -> float:
    """Total variation for unordered categories, Earth Mover's for ordered ones."""
    p = p / p.sum(); q = q / q.sum()
    if not ordered:
        return float(0.5 * np.abs(p - q).sum())
    support = np.arange(p.size, dtype=float)
    return float(wasserstein_distance(support, support, p, q) / max(p.size - 1, 1))

Step 4 — Route failing cells to generalization, not straight to suppression # permalink

A cell that fails diversity has three remedies, in increasing cost: merge it with a neighbour so the union is diverse; coarsen the attribute so “oncology” becomes “specialist outpatient”; or suppress it. Attribute coarsening is usually the cheapest for the reader and the one teams reach for last.

def remedy(cell: str, l_eff: float, t_dist: float, l_min: float, t_max: float) -> str:
    if l_eff >= l_min and t_dist <= t_max:
        return "publish"
    if l_eff >= l_min * 0.6:
        return "coarsen_attribute"      # a coarser taxonomy usually clears both
    return "merge_or_suppress"

Step 5 — Record the reference scope in the release metadata # permalink

A t-closeness figure is meaningless without knowing what it was compared against. A cell that is close to its neighbourhood and far from the city is a different claim than the reverse, and only one of them is what your reader will assume.

Validation & Re-identification Testing # permalink

Posterior-shift simulation. The direct test: for each published cell, compute an adversary’s prior over the sensitive value (the reference distribution) and their posterior after learning the cell. Report the maximum shift across cells. This is what the parameters are proxies for, and it catches configurations where $l$ and $t$ both pass while one value’s probability triples.

Homogeneity sweep over cell size. Coarsening a grid raises k monotonically and does not raise diversity monotonically — merging two homogeneous cells with the same value leaves a larger homogeneous cell. Plot both against resolution before choosing one.

Person-level re-check. Recompute the distributions counting each individual once and compare. A large gap means the row-level figures were driven by frequent visitors.

Cross-attribute check. Diversity in one attribute does not protect a correlated second one. A cell diverse in “service type” but homogeneous in “facility id” discloses through the second, and the second is usually publishable-looking metadata.

Common Failure Modes & Gotchas # permalink

Using distinct l-diversity. It counts values, not weight, and passes the skewed cell that motivates the whole exercise. Use entropy diversity and report the effective count.

Total variation on an ordered attribute. It ignores how far apart the values are, so a cell concentrated at one end of an income scale scores the same as one spread evenly across adjacent bands.

A global reference in a heterogeneous city. Forcing every cell to look like the city-wide mix suppresses exactly the districts whose composition is the reason the map is being made. Use a local reference and say so.

Applying the tests before k. Diversity is a property of a published cell. Running it on raw points measures the neighbourhood, not the release.

Treating the sensitive attribute as the only one. Any column an adversary could treat as sensitive counts, including ones that look operational. Declare the set explicitly.

Suppressing first. Attribute coarsening clears most failures at a fraction of the coverage cost, and it is reversible in the design if it turns out to lose too much.

Where These Tests Sit in a Release Pipeline # permalink

The order matters and it is not the order the definitions suggest. Identity protection comes first, attribute protection second, and both come after the geometry is fixed.

Bin, then floor, then diversify. Diversity is a property of a published cell, so it can only be measured once the cells exist and once the sub-threshold ones have been removed. Running it earlier measures the neighbourhood rather than the release. Running it on cells that will later be merged measures a partition that will not be published.

Coarsen the attribute before coarsening the geography. A failing cell has two cheap remedies and one expensive one. Attribute coarsening keeps the cell, its count and its location, and costs only category detail. Merging keeps the attribute and costs spatial resolution. Suppression costs everything and additionally marks the map. Most pipelines reach for the third because the failing test names a cell rather than naming a remedy — returning the remedy from the scoring pass is a small change that reorders the whole decision.

Re-measure after every remedy. Coarsening the taxonomy changes every cell’s distribution, not only the failing ones, and it can lower diversity where two coarse values merge activities that used to be distinct. A single pass is not enough; run to a fixed point, and cap the number of iterations so a pathological taxonomy fails loudly rather than looping.

Record the reference scope with the thresholds. A t-closeness figure measured against a neighbourhood ring and one measured against the whole release are different claims about the same cell, and a reviewer shown only the number has no way to tell which they were given.

Compliance Alignment # permalink

The reference scope belongs in the assessment alongside the thresholds. A reviewer who is shown $t = 0.2$ without being told whether the comparison was global or local has not been shown the control.

FAQ # permalink

Do I need t-closeness if I already enforce l-diversity?

If the sensitive attribute is ordered, or if its global distribution is very uneven, yes. l-diversity counts how many values a cell contains and is satisfied by a cell that is 90% one value. t-closeness constrains the weights, which is what stops the posterior from moving.

How do I pick $t$?

Work backwards from an acceptable posterior shift. A total-variation distance of $t$ bounds how far any single value’s probability can move, so $t = 0.2$ corresponds to a shift of at most twenty percentage points on any value. Pick the shift a reviewer would accept and use it directly.

What if a whole district fails?

That is usually a signal that the attribute taxonomy is too fine rather than that the district must be dropped. Coarsen the values first; suppressing a hospital district from a health-access map removes the finding the map exists to show.

Does adding noise to counts help instead?

It helps against the count-based attacks but not against homogeneity: a cell whose noisy counts are all attached to one value still discloses the value. Noise and diversity address different disclosures, and a release with a sensitive attribute generally needs both — see small-cell suppression and complementary rules for the count side.

Related # permalink

• Enforcing l-Diversity on POI Categories Within Grid Cells — the implementation and its verification
• k-Anonymity Grouping for Location Traces — the identity-protection layer these tests sit on top of
• Small-Cell Suppression & Complementary Rules — the count-disclosure counterpart
• Scoring POI Sensitivity for Location Datasets — deciding which attribute values are sensitive in the first place
• Sector-Specific k-Anonymity Thresholds for Location Data — where the k floor comes from

← Back to Geospatial Masking & Perturbation Techniques