Lowering the cost of anonymization

Notations

Mathematical notations

$N$	The set of nonnegative integers
$Z$	The set of integers
$R$	The set of real numbers
$\left|E\right|$	Cardinality of set $E$
$E\setminus F$	Set difference of set $E$ and set $F$
$E\times F$	Cartesian product between set $E$ and set $F$
$P\left[A\right]$	Probability of event $A$
$P\left[A,B\right]$	Probability of the conjunction of event $A$ and event B
$\theta$	A probability distribution (or ${\theta }_1$, ${\theta }_2$, …).
$P_{X\sim \theta }\left[A\left(X\right)\right]$	Probability of event $A\left(X\right)$, when $X$ is sampled from $\theta$
$P\left[A|B\right]$	Probability of event $A$, conditioned on event $B$
$E\left[L\right]$	Expected value of random variable $L$
$E_{X\sim \theta }\left[L\left(X\right)\right]$	Expected value of $L\left(X\right)$, when $X$ is sampled from $\theta$
${\theta }_{|B}$	Probability distribution $\theta$ conditioned on event $B$
$A{\left(X\right)}_{|X\sim \theta ,B\left(X\right)}$	Random variable $A\left(X\right)$, when $X$ is sampled from ${\theta }_{|B\left(x\right)}$
$f:E\to F$	Function, possibly probabilistic, from set $E$ to set $F$

Notations for datasets and records

$T$	Set of possible records
$t\in T$	A record (or $t_1$, $t_2$, …)
$D=T^{\ast }$	Set of possible datasets (sequences of records)
$D\in D$	A dataset (or $D_1$, $D_2$, $\hat{D}$, …)
$\left|D\right|\in N$	The number of records in dataset $D$ (typically denoted $n$)
$D\left(i\right)$	The $i$-th record of dataset $D$ ($i\le \left|D\right|$)
$D_{-i}$	Dataset $D$ with its $i$-th record removed

Some of these notations are slightly modified when we introduce the concept of record ownership in Chapter 4, see the “Datasets with user identifiers” notation table further down.

Differential privacy and its variants

$O$	Set of possible outputs of a privacy mechanism
$O\in O$	An output of the privacy mechanism
$S\subseteq O$	A subset of outputs of a privacy mechanism
$M:D\to O$	A privacy mechanism
${\approx }_{\epsilon }$	$\epsilon$-indistinguishability (see Definition 5)
${\approx }_{\epsilon ,\delta }$	$\left(\epsilon ,\delta \right)$-indistinguishability (see Definition 14)
$L_{M\left(D_1\right)∕M\left(D_2\right)}$	Privacy loss random variable (PLRV) between $M\left(D_1\right)$ and $M\left(D_2\right)$, often abbreviated $L_{D_1∕D_2}$ (see Definition 13)
$B$	Set of possible partial knowledges
$B\in B$	A value of the partial knowledge (or $B_1$, $B_2$, $\hat{B}$, …)
$\Theta$	Family of probability distributions on $D$ or $D\times B$
$\theta \in \Theta$	A probability distribution on $D$ or $D\times B$, also used as an abbreviation for $D\sim \theta$ or $\left(D,B\right)\sim \theta$, e.g. in $P_{\theta }\left[\text{…}\right]$ or $M{\left(D\right)}_{|\theta }$
$\pi$	A probability distribution on $T$
$\hat{D}$	A specific dataset, also used as an abbreviation for the event $D=\hat{D}$
$\hat{B}$	A specific value of the partial knowledge, also used as an abbreviation for the event $B=\hat{B}$
$\mathrm{Sim}$	A function from $D$ to $O$ called a simulator (see Definition 50)
$D_{i\to t^{\text{'}}}$	Dataset $D$ with its $i$-th record replaced by $b\in T$
$\hat{\theta }$	A normalization of a distribution $\theta$ (see Definition 53)
${\varphi }_0$, ${\varphi }_1$, …	Parameters of a normalization $\hat{\theta }$ (see Definition 53)
$L_{i\leftarrow t∕i\leftarrow t^{\text{'}}}^{M,\theta }(O,\hat{B})$	Privacy loss random variable (PLRV) of an output $O$ given partial knowledge $\hat{B}$, when distinguishing between $D\left(i\right)=t$ or $D\left(i\right)=t^{\text{'}}$ (see Definition 56)
$m\left(O,B\right)$	Abbreviation for $\text{max}\left(0,1-e^{\epsilon -L_{i\leftarrow t∕i\leftarrow t^{\text{'}}}^{M,\theta }(O,B)}\right)$
${\text{APK}}_{i,t,t^{\text{'}},\hat{B}}$	Abbreviation for $\underset{{\theta }_{|D\left(i\right)=t,\hat{B}},O\sim M\left(D\right)}{E}\left[m\left(O,\hat{B}\right)\right]$
${\text{PPK}}_{i,t,t^{\text{'}}}$	Abbreviation for $\underset{{\theta }_{|D\left(i\right)=a},O\sim M\left(D\right)}{E}\left[m\left(O,B\right)\right]$
${\phi }_{B_1,B_2}^i$	Bijective mapping between $B_1$ and $B_2$ for record $i$ (see Definition 59)
${\text{Dep}}_{i,t,t^{\text{'}}}^{M_1,M_2,\theta }$	Dependency of $M_2$ on $M_1$ to distinguish $D\left(i\right)=t$ and $D\left(i\right)=t^{\text{'}}$ (see Definition 62)

Cardinality estimators

$E\subseteq T$	A set of records (or $E_1$, $E_2$, …)
$S$	Set of possible sketches
$S\in S$	A sketch (or $S^{\text{'}}$, $S_1$, $S_2$, …)
$S$	Set of probability distributions over $S$
$\sigma \in S$	A probability distribution over sketches (or ${\sigma }^{\text{'}}$)
$S_{\text{∅}}\in S$	The empty sketch
$\mathrm{add}\left(t,S\right)$	Sketch (or distribution of sketches), obtained by adding record $t$ to a sketch (or distribution of sketches) $S$
$\mathrm{estimate}\left(S\right)$	Estimated number of distinct records added to a sketch $S$
$S_E\in S$	Sketch obtained by adding all records of set $E$ into $S_{\text{∅}}$
${\sigma }_E\in S$	Distribution of sketches obtained by adding records of set $E$ to $S_{\text{∅}}$
$\mathrm{merge}\left(S,S^{\text{'}}\right)$	Sketch obtained by merging sketches $S$ and $S^{\text{'}}$
$\mathrm{merge}\left(\sigma ,{\sigma }^{\text{'}}\right)$	Distribution of sketches obtained by merging distributions of sketches $\sigma$ and ${\sigma }^{\text{'}}$ (also denoted $\sigma \cdot {\sigma }^{\text{'}}$)
$P_n\left(T\right)$	Set of subsets of $T$ of cardinality $n$
$P_n\left[A\left(E\right)\right]$	Probability of event $A\left(E\right)$, when $E$ is taken uniformly in $P_n\left(T\right)$

Datasets with user identifiers

$C$	A dataset column (or $C_1$, $C_2$, …)
$c\in C$	The value of a column (or $c_1$, $c_2$, …)
$I$	Set of possible user identifiers
$\mathrm{id}$	A user identifier (or ${\mathrm{id}}_1$, ${\mathrm{id}}_2$, …)
$I\left[c_j\right]$	The set of user identifiers associated with a column value
$h$	A hash function
$T=C_1\times \cdots \times C_a$	Set of possible records, composed of multiple columns
$\left(\mathrm{id},t\right)\in I\times T$	A row, associating a user identifier with a record
$D$	A dataset, formally a multiset of rows
$\parallel D_1-D_2\parallel$	Row-level distance between datasets $D_1$ and $D_2$ (see Definition 78)
${\parallel D_1-D_2\parallel }_u$	User-level distance between datasets $D_1$ and $D_2$ (see Definition 78)
$f:D\to R^d$	A vector-valued function
${\parallel v\parallel }_1$	$L^1$ norm of vector $v\in R^d$
$\Delta f$	$L^1$-sensitivity of function $f$ (see Definition 80)
${\Delta }_{u}f$	User-level $L^1$-sensitivity of function $f$ (see Definition 80)