how many people are pinned down by k points of their trace

The measurement from de Montjoye et al.'s *Unique in the Crowd*: give an attacker `k` (place, time) points drawn from somebody's trace and ask how often that narrows the population to a single individual. Sweeping `k` and the recording resolution says how much coarsening it takes to make a mobility-style data set safe – and, in the original paper, the answer was "more than you would think": four points identified 95

Usage

spatiotemporal_unicity(
  dat,
  id = "ID",
  place = "PLACE",
  time = "TIME",
  k = 1:4,
  time_resolution = 1,
  space_resolution = 1,
  n_samples = 20,
  seed = 0L
)

Arguments

dat: a transaction-shaped data frame: one row per event, several rows per individual
id: name of the column identifying the individual
place: name of the location column
time: name of the timestamp column
k: number of known points to evaluate (default `1:4`, the range the original paper reports)
time_resolution: numeric vector of time bin widths, in the units of `time`; every combination with `space_resolution` is evaluated
space_resolution: numeric vector of location-merging factors; see [coarsen_place()]
n_samples: maximum number of point subsets drawn per individual (default 20). Individuals for whom `choose(trace, k)` is no larger than this are enumerated exhaustively instead, which makes them exact.
seed: integer seed for the subset sampling (default 0L, so a plain call is reproducible); NULL uses the ambient RNG stream

Value

a data frame with one row per `(k, time_resolution, space_resolution)` combination and columns

k, time_resolution, space_resolution: the setting
n_individuals: individuals in `dat`
n_evaluated: those with at least `k` distinct points
n_points: distinct (place, time) points at this resolution
exhaustive: TRUE when every evaluated individual had all their point subsets enumerated, so the row is exact rather than sampled
unicity: fraction pinned down to exactly one individual
expected_id_rate: mean of `1 / anonymity set size` – what an attacker guessing inside the set achieves
mean_anonymity_set: mean number of individuals matching the `k` points

What it bounds

`unicity` is the fraction pinned down with *certainty*, so it is a lower bound on what an attack achieves, not an upper one (this was established by measurement in Issue #21). An individual sharing their `k` points with `m - 1` others counts 0 towards `unicity`, but an attacker guessing inside that anonymity set still wins with probability `1/m`. `expected_id_rate` reports exactly that, and is always at least `unicity`. Read the pair, not `unicity` alone.

Individuals with short traces

An attacker cannot hold `k` distinct points of somebody who only ever visited `k - 1`, so at each `k` the measurement covers only the individuals with at least `k` distinct points. `n_evaluated` reports how many that was: when it falls well below `n_individuals` the row describes the frequent visitors rather than the population, and those are the people a trace-based attack works on anyway.

Examples