Estimating the Uniqueness of Mobility Traces

To estimate how identifiable a mobility dataset is, measure its unicity: the fraction of individuals whose trace is singled out by only p spatio-temporal points at a chosen spatial and temporal resolution — a quantity that, for typical human movement, reaches the large majority of the population at around four points.

Core Calculation # permalink

A mobility trace is a set of visited spatio-temporal cells. Fix a spatial resolution (cell size) and a temporal resolution (time-bin width); every raw ping collapses to a tuple (cell, time_bin). A signature is a random subset of p such tuples drawn from one person’s trace.

An individual is unique for that signature when no other individual in the population contains all p tuples. Unicity is the expected fraction of unique individuals:

where N is the population size, $S_i^{(p)}$ is a random p-point signature drawn from individual i’s trace $T_i$, and the expectation is over the random choice of points. Here $\varepsilon_p$ denotes the unicity fraction — unrelated to the privacy budget of the same symbol elsewhere on this site.

A useful closed-form intuition comes from treating the p chosen cells as independent. If a single random cell is shared with a uniformly chosen other person with probability q, then the chance that a specific other person matches all p points is $q^p$, and the probability that nobody among the remaining N-1 people matches is:

Because q is small (most cells are rare) and it is raised to the p, the collision probability $q^p$ collapses geometrically as p grows. This is why unicity climbs so steeply: adding a point does not add risk linearly, it multiplies away the surviving matches.

The empirical scaling with resolution follows a power law. If $\varepsilon_p$ is the unicity at the native resolution and the grid is coarsened by a factor v on both axes, the residual unicity decays approximately as:

with a small exponent (published mobile-phone studies report $\beta \approx 0.1$). A small $\beta$ is the bad news for data stewards: you must coarsen enormously to gain a little.

Worked numeric example # permalink

Take an hourly, antenna-resolution phone dataset with N = 1,500,000 subscribers. Suppose the probability that a random person shares any one specific (antenna, hour) cell with you is q = 0.01.

• p = 2: $q^p = 10^{-4}$, so $\Pr[\text{unique}] \approx (1 - 10^{-4})^{1{,}499{,}999} \approx e^{-150} \approx 0$. Almost nobody is unique — collisions abound.
• p = 4: $q^p = 10^{-8}$, so $\Pr[\text{unique}] \approx (1 - 10^{-8})^{1{,}499{,}999} \approx e^{-0.015} \approx 0.985$. About 98.5% are unique.
• p = 5: $q^p = 10^{-10}$, so $\Pr[\text{unique}] \approx e^{-0.00015} \approx 0.9998$.

The jump from p = 2 to p = 4 moves the population from effectively anonymous to almost fully identifiable — the signature of the celebrated “four points” result. Note the sensitivity to q: a denser common cell (larger q, say people bunched at a transit hub) lowers unicity for the same p, which is the mechanism every defense exploits.

Python Implementation # permalink

The routine below estimates unicity directly from a trace table by Monte Carlo sampling. It underpins any re-identification risk assessment for geospatial datasets that must report how many known points compromise a release.

import numpy as np
import pandas as pd
from typing import Iterable

# CRS note: input coordinates are WGS84 (EPSG:4326). Spatial discretization
# uses a metric grid, so reproject to a local UTM zone (e.g. EPSG:32633)
# BEFORE calling this function so that `spatial_m` is a true metre cell size.


def estimate_unicity(
    traces: pd.DataFrame,
    p_values: Iterable[int],
    spatial_m: float,
    temporal_s: float,
    n_samples: int = 200,
    seed: int | None = None,
) -> pd.DataFrame:
    """
    Estimate unicity (fraction of uniquely identifiable individuals) as a
    function of the number of known spatio-temporal points p, at a given
    spatial and temporal resolution.

    Args:
        traces: columns ['uid', 'x', 'y', 't'] in a PROJECTED metric CRS,
            with 't' as epoch seconds.
        p_values: signature lengths to evaluate (e.g. range(1, 8)).
        spatial_m: grid cell edge length in metres (privacy knob: larger
            cells lower unicity by merging distinct places).
        temporal_s: time-bin width in seconds (larger bins merge visits).
        n_samples: Monte Carlo repetitions per p to average over the random
            choice of which points an attacker knows.
        seed: RNG seed for reproducible risk reports.

    Returns:
        DataFrame ['p', 'unicity'] — the unicity curve.
    """
    rng = np.random.default_rng(seed)

    # 1. Discretize to the spatio-temporal grid. Coarser cells => stronger
    #    privacy, because more people collide into the same signature tuple.
    df = traces.copy()
    df["cell"] = (
        (df["x"] // spatial_m).astype("int64").astype(str) + ":" +
        (df["y"] // spatial_m).astype("int64").astype(str) + ":" +
        (df["t"] // temporal_s).astype("int64").astype(str)
    )

    # 2. Each individual -> set of distinct visited cells (their trace).
    user_cells = df.groupby("uid")["cell"].agg(lambda s: frozenset(s))
    users = user_cells.index.to_numpy()

    # Inverted index: cell -> set of users, to count competing matches fast.
    cell_to_users: dict[str, set] = {}
    for uid, cells in user_cells.items():
        for c in cells:
            cell_to_users.setdefault(c, set()).add(uid)

    rows = []
    for p in p_values:
        eligible = [u for u in users if len(user_cells[u]) >= p]
        if not eligible:
            rows.append({"p": p, "unicity": float("nan")})
            continue

        unique_hits = 0
        trials = 0
        for _ in range(n_samples):
            u = eligible[rng.integers(len(eligible))]
            cells = list(user_cells[u])
            sig = rng.choice(len(cells), size=p, replace=False)
            signature = [cells[i] for i in sig]

            # Intersect the user sets of each signature cell: anyone left
            # (besides u) also carries all p points => u is NOT unique.
            matches = cell_to_users[signature[0]].copy()
            for c in signature[1:]:
                matches &= cell_to_users[c]
                if len(matches) <= 1:
                    break
            if len(matches) <= 1:  # only u itself remains
                unique_hits += 1
            trials += 1

        rows.append({"p": p, "unicity": unique_hits / trials})

    return pd.DataFrame(rows)

Verification # permalink

Confirm the estimator with a controlled synthetic population whose answer you know, then sanity-check the shape of the curve.

# Build a population where every user has one shared "commuter hub" cell plus
# private cells. With p high enough to include a private cell, unicity -> 1.
rng = np.random.default_rng(0)
records = []
for uid in range(2000):
    # 3 shared hub cells (low uniqueness) + 5 private cells (high uniqueness)
    for _ in range(6):
        records.append((uid, rng.integers(0, 3) * 500.0, 0.0, 3600))      # hubs
    for _ in range(5):
        records.append((uid, (10_000 + uid) * 1.0, uid * 7.0, uid * 60))   # private
traces = pd.DataFrame(records, columns=["uid", "x", "y", "t"])

curve = estimate_unicity(traces, p_values=range(1, 6),
                         spatial_m=100.0, temporal_s=3600.0, seed=1)
print(curve)

# Verification checklist:
# [ ] unicity is monotonically non-decreasing in p (more points never help privacy)
assert (curve["unicity"].diff().dropna() >= -1e-9).all()
# [ ] unicity at p=1 is well below unicity at max p (hubs mask single points)
assert curve["unicity"].iloc[0] < curve["unicity"].iloc[-1]
# [ ] every reported value is a valid probability in [0, 1]
assert curve["unicity"].between(0, 1).all()

The three assertions catch the common implementation faults: a non-monotonic curve signals a sampling or intersection bug, a flat curve signals that discretization collapsed every point into one cell, and an out-of-range value signals a counting error.

Edge Cases & Adjustments # permalink

• Sample versus population. Unicity measured on a 1% sample is not the population identifiability. In a sample, an individual can look unique only because their true match was not sampled. Report within-sample uniqueness and population identifiability as distinct figures, and never present a sample estimate as an upper bound on real-world risk.
• Temporal binning dominates. Widening temporal_s from one hour to one day often lowers unicity more than any spatial coarsening, because visit timing carries most of the discriminative signal. Sweep the temporal axis first when tuning a release.
• Sparse and heavy travellers. Users with very few points cannot be evaluated at large p (filtered out above), while frequent travellers with many rare cells inflate the tail. Report unicity per activity-level stratum rather than one pooled number.
• Projection choice. Discretizing in raw WGS84 degrees produces cells that shrink toward the poles, biasing unicity across latitudes. Reproject to a local UTM zone so that spatial_m is an honest metre value before gridding.

FAQ # permalink

Why do only about four points identify most people?

Human mobility is heavy-tailed and habitual. A handful of recurrent places plus their timing forms a signature almost no one else shares, so the probability that anyone matches all p points falls off as a power of p. Around four antenna-and-hour points, that surviving-match probability crosses below one person for realistic populations.

How does coarsening the grid change unicity?

It lowers it, but along a shallow power law. Because the exponent is small, halving precision on both axes buys only a modest reduction. Meaningful protection usually requires combining aggressive aggregation with suppression or grouping rather than resolution changes alone.

Is unicity the same as k-anonymity?

They are two views of the same equivalence-class structure. A trace is unique when its class under the chosen p points has size one — that is, k = 1. Estimating unicity tells you how far a dataset sits from any target k, which is why it feeds naturally into k-anonymity grouping for location traces.

Does a low sample unicity mean my data is safe to publish?

No. Sample unicity systematically understates the identifiability an adversary holding the full population can achieve. Treat it as a floor for concern, not a ceiling on risk, and re-estimate against the release population you actually intend to publish.

Related

• Re-identification Risk Assessment for Geospatial Datasets — the parent workflow this estimate feeds into
• k-anonymity grouping for location traces — turning a unicity finding into a minimum class size
• Trajectory Anonymization Techniques — reshaping traces once unicity flags them as identifiable
• Spatial Privacy Fundamentals & Threat Modeling — where trace uniqueness sits in the wider threat model

← Back to Re-identification Risk Assessment for Geospatial Datasets