Hands-On Differential Privacy

Appendix A. Supplementary Definitions

Cardinality

The cardinality of a data set is the number of instances (rows) in a data set $x$, denoted $|x{|}_C$.

Metric

A metric $d(a,b)$ is a function $d:𝔻\times 𝔻\to ℝ$ such that for any points $a$, $b$, and $c$ in a domain $𝔻$, the following properties hold:

• $d(a,b)\ge 0$ and $d(a,b)=0$, if and only if $a=b$ (non-negativity)

• $d(a,b)=d(b,a)$ (symmetry)

• $d(a,c)\le d(a,b)+d(b,c)$ (triangle inequality)

  Keep in mind that some of the metrics used in differential privacy don’t satisfy all of these axioms. For instance, in the setting of unbounded contributions where data sets have user IDs (see “Data Sets with Unbounded Contributions”), two different data sets may still have an identifier distance of zero.

Multisets

Multisets are data sets that can have multiple instances of each record. Unlike vectors, multisets don’t care about row ordering.

Symmetric difference

The symmetric difference between multisets $x$ and $x^{\prime }$ is the multiset of elements that are either in $x$ or $x^{\prime }$, but not in their intersection. The symmetric difference between sets $x$ and $x^{\prime }$ is denoted $x△x^{\prime }$. That is, the symmetric difference consists of those elements that do not have matches in the other data set.