Lowering the cost of anonymization

Proof. The proof is comprised of three steps, following the intuition previously given.

1.

We show that a sketch $S_E$, computed from a random set $E$ with an $\epsilon$-sketch private estimator above cardinality $N$, will ignore many records after $N$ (Lemma 4).

2.

We prove that if a cardinality estimator ignores a certain ratio of records after adding $n=N$ records, then it will ignore an even larger ratio of records as $n$ increases (Lemma 5).

3.

We conclude by proving that an unbiased cardinality estimator that ignores many records must have a large variance (Lemma 6).

The theorem follows directly from these lemmas. □

Proof. We first prove that such an estimator also satisfies

$$P_n\left[\mathrm{add}\left(S_E,t\right)=S_E|t\in E\right]\le e^{\epsilon }\cdot P_n\left[\mathrm{add}\left(S_E,t\right)=S_E|t\notin E\right].$$

We decompose the left-hand side of the inequality over all possible values of $S_E$ which that $\mathrm{add}\left(S_E,t\right)=S_E$. If we abbreviate this set $I_t=\left\{M|\mathrm{add}\left(S,t\right)=S\right\}$, we have:

$$\begin{array}{cccc}{P}_n\left[\mathrm{add}\left(S_E,t\right)=S_E|t\in E\right]& ={\sum }_{S\in I_t}{P}_n\left[S_E=S|t\in E\right]& & \\ & \le e^{\epsilon }\cdot {\sum }_{S\in I_t}{P}_n\left[S_E=S|t\notin E\right]& & \\ & \le e^{\epsilon }\cdot P_n\left[\mathrm{add}\left(S_E,t\right)=S_E|t\notin E\right],& & \end{array}$$

where the first inequality is obtained directly from the definition of $\epsilon$-sketch privacy.

Now, Lemma 2 gives $P_{\mathrm{add}\left(S_E,t\right)=S_E}\left[t\in E\right]=1$, and finally:

$$P_n\left[\mathrm{add}\left(S_E,t\right)=S_E|t\notin E\right]\ge e^{-\epsilon }.$$

□

Proof. First, note that if $F\subseteq E$, and $\mathrm{add}\left(S_F,t\right)=S_F$, then $\mathrm{add}\left(S_E,t\right)=S_E$. This is a direct consequence of Lemma 3: $S_E=\mathrm{merge}\left(S_{E\setminus F},S_F\right)$, so:

$$\begin{array}{cccc}\mathrm{add}\left(S_E,t\right)& =\mathrm{merge}\left(S_{E\setminus F},\mathrm{add}\left(S_F,t\right)\right)& & \\ & =\mathrm{merge}\left(S_{E\setminus F},S_F\right)& & \\ & =S_E& & \end{array}$$

We show next that when $n\ge k\cdot N$, generating a set $E\in P_n\left(T\right)$ uniformly randomly can be seen as generating $k$ independent sets in $P_N\left(T\right)$, then merging them. Indeed, generating such a set can be done by as follows:

1.

For each $i\in \left\{1,\dots ,k\right\}$, generate a set $E_i\subseteq P_N\left(T\right)$ uniformly randomly, then take the union of all these sets: $E_{\cup }={\bigcup }_i{E}_i$.

2.

If some records appear in multiple $E_i$, the total cardinality might be lower than $n$, so we need add records uniformly at random to reach the desired cardinality: calculate $d=\left|E_{\cup }\right|$, then generate a set $E^{\text{'}}\in P_{n-d}\left(T\setminus E_{\cup }\right)$ uniformly randomly.

3.

Add the missing items to complete the set: $E=E_{\cup }\cup E^{\text{'}}$.

Step 1 ensures that we used $k$ independent sets of cardinality $N$ to generate $E$, and step 2 and 3 ensure that $E$ has exactly $n$ records.

Intuitively, each time we generate a set $E_i$ of cardinality $N$ uniformly at random in $T$, we have one chance that $t$ will be ignored by $E_i$ (and thus by $E$). So $t$ can be ignored by $S_E$ with a certain probability because it was ignored by $S_{E_1}$. Similarly, it can also be ignored because of $S_{E_2}$, etc. Since the choice of $E_i$ is independent of the choice of records in ${\bigcup }_{j\iff i}{E}_j$, we can rewrite:

$$\begin{array}{cccc}{P}_n\left[\mathrm{add}\left(S_E,t\right)\iff S_E|t\notin E\right]& \le \prod _{i=1}^k{P}_n\left[\mathrm{add}\left(S_{E_i},t\right)\iff S_{E_i}|t\notin E\right]& & \\ & \le \prod _{i=1}^k\left(1-P_n\left[\mathrm{add}\left(S_{E_i},t\right)=S_{E_i}|t\notin e_i\right]\right)& & \\ & \le {\left(1-p\right)}^k& & \end{array}$$

using the hypothesis of the lemma. Thus:

$$P_n\left[\mathrm{add}\left(S_E,t\right)=S_E|t\notin E\right]\ge 1-{\left(1-p\right)}^k.$$

□

Proof. The proof’s intuition is as follows. The hypothesis of the lemma requires that the cardinality estimator, on average, ignores a proportion $1-p$ of new records added to a sketch (once $N$ records have been added): the sketch is not changed when a new record is added. The best thing that the cardinality estimator can do, then, is to store all records that it does not ignore, count the number of unique records among these, and multiply this number by $1∕p$ to correct for the records ignored. It is well-known that estimating the size $k$ of a set based on the size of a uniform sample of sampling ratio $p$ has a variance of $\frac{1-p}{p}k$. Hence, our cardinality estimator has a variance of at least $\frac{1-p}{p}\left(n-N\right)$.

Formalizing this idea requires some additional technical steps, and the proof is decomposed into three steps. In Step 1, we fix the first $N$ records added to the sketch, and we bound the variance of the estimator that has these records as initial input. In Step 2, we explicitly compute the probability for an record $t$ to be ignored by $S_E$, first when $t$ is fixed, then when $E$ is fixed. We then use these results in Step 3 to average the bound over all possible choices for the $N$ records in $E$, which gives us an overall bound.

Step 1: Bound the estimator variance.

Let $E\in P_N\left(T\right)$. Let $X_E=\left\{t\in T|\mathrm{add}\left(S_E,t\right)\iff S_E\right\}$ be the set of records that are not ignored by $S_E$. Let $p_E=\frac{\left|X_E\right|}{\left|T\right|}$, or equivalently, let $p_E=P_t\left[\mathrm{add}\left(S_E,t\right)\iff S_E|t\notin E\right]$, where $P_t$ is the distribution that picks $t$ uniformly randomly in $T$.

$X_E$ can be seen as the sampling set of the estimator with $E$ as initial input, while $p_E$ can be seen as its sampling fraction: all other records are discarded, so the estimator only has access to records in $E$ and $X_E$ to compute its estimate.

The optimal estimator to minimize variance in this context simply counts the exact number of distinct records in the sample (remembering each one), and divides this number by $p_E$ to estimate the total number of distinct records.²

What is the variance $V_{n|E}$ of this optimal estimator? Suppose we added $n-N$ records after reaching the sampling part. The number of records in the sample is a random variable with variance $p_E\left(1-p_E\right)\left(n-N\right)$. Dividing this random variable by $p_E$ gives a variance of $\frac{1-p_E}{p_E}\cdot \left(n-N\right)$. Thus:

$$V_{n|E}\ge \frac{1-p_E}{p_E}\cdot \left(n-N\right).$$

Since the first $N$ records are chosen uniformly at random, the variance of the overall estimator is bounded by their average. If we denote by $P_N\left(T\right)$ the set of all possible subsets $E\subseteq T$ of cardinality $N$, we have:

$$V_n\ge {\mathrm{avg}}_{E\in P_N\left(T\right)}\frac{1-p_E}{p_E}\left(n-N\right)$$

(3.1)

where $\mathrm{avg}$ stands for the average.

Step 2: Intermediary results.

Fix $E\in P_N\left(T\right)$. Denoting by $1_X$ the function whose value is 1 if $X$ is satisfied and 0 otherwise,

$$\begin{array}{cccc}{P}_t\left[\mathrm{add}\left(S_E,t\right)\iff S_E|t\notin E\right]& =\frac{P_t\left[\mathrm{add}\left(S_E,t\right)\iff S_E,t\notin E\right]}{P_t\left[t\notin E\right]}& & \\ & =\frac{\left|T\right|}{\left|T\right|-N}\cdot {\mathrm{avg}}_{t\in T}\left(1_{\mathrm{add}\left(S_E,t\right)\iff S_E}\right).& \text{(3.2)}& \end{array}$$

Indeed, $P_t\left[t\notin E\right]=\frac{\left|T\right|-N}{\left|T\right|}$ is straightforward, and since $t\in E$ implies $\mathrm{add}\left(S_E,t\right)=S_E$, the condition $\mathrm{add}\left(S_E,t\right)\iff S_E,t\notin E$ can be simplified to $\mathrm{add}\left(S_E,t\right)\iff S_E$.

Now, fix $t\in T$. Then

$$\begin{array}{cccc}{P}_N\left[\mathrm{add}\left(S_E,t\right)\iff S_E|t\notin E\right]& =\frac{P_N\left[\mathrm{add}\left(S_E,t\right)\iff S_E,t\notin E\right]}{P_N\left[t\notin E\right]}& & \\ & =\frac{\left|T\right|}{\left|T\right|-N}\cdot {\mathrm{avg}}_{E\in P_N\left(E\right)}\left(1_{\mathrm{add}\left(S_E,t\right)\iff S_E}\right).& \text{(3.3)}& \end{array}$$

Indeed, we have

$$\begin{array}{cccc}{P}_N\left[t\notin E\right]& =\left(\frac{\left|T\right|-1}{N}\right)\cdot {\left(\frac{\left|T\right|}{N}\right)}^{-1}& & \\ & =\frac{\left(\left|T\right|-1\right)!}{\left(\left|T\right|-1-N\right)!N!}\cdot \frac{\left(\left|T\right|-N\right)!N!}{\left|T\right|!}=\frac{\left|T\right|-N}{\left|T\right|}.& & \end{array}$$

Step 3: Conclude using convexity.

We now prove that ${\mathrm{avg}}_{E\in P_N\left(T\right)}\left(p_E\right)\le p$. Our initial hypothesis states that for all $t$, we have $p\ge P_N\left[\mathrm{add}\left(S_E,t\right)\iff S_E|t\notin E\right]$. We can average this for every $t$ and use (3.3) and (3.2):

$$\begin{array}{cccc}p& \ge & {\mathrm{avg}}_{t\in T}\left(P_N\left[\mathrm{add}\left(S_E,t\right)\iff S_E|t\notin E\right]\right)& \\ & \stackrel{\text{(3.3)}}{=}& {\mathrm{avg}}_{t\in T}\left(\frac{\left|T\right|}{\left|T\right|-N}\cdot {\mathrm{avg}}_{E\in P_N\left(E\right)}\left(1_{\mathrm{add}\left(S_E,t\right)\iff S_E}\right)\right)& \\ & =& {\mathrm{avg}}_{E\in P_N\left(T\right)}\left(\frac{\left|T\right|}{\left|T\right|-N}\cdot {\mathrm{avg}}_{t\in T}\left(1_{\mathrm{add}\left(S_E,t\right)\iff S_E}\right)\right)& \\ & \stackrel{\text{(3.2)}}{=}& {\mathrm{avg}}_{E\in P_N\left(T\right)}\left(P_t\left[\mathrm{add}\left(S_E,t\right)\iff S_E|t\notin E\right]\right)& \\ & \ge & {\mathrm{avg}}_{E\in P_N\left(T\right)}\left(p_E\right)& \text{(3.4)}\end{array}$$

Now, using (3.1) and (3.4) along with the fact that the function $x\to \frac{1-x}{x}\cdot \left(n-N\right)$ is convex and decreasing on $\left(0,1\right)$, we can conclude by Jensen’s inequality that

$$V_n\ge \frac{1-p}{p}\left(n-N\right).$$

□

Proof. By the properties required from probabilistic cardinality estimators in Definition 67, the $\mathrm{merge}$ operation is commutative and associative on the family $\left\{{\sigma }_E|E\subseteq T\right\}$. By linearity of the $\mathrm{merge}$ operation, these properties are preserved for any linear combination of vectors ${\sigma }_E$. □

Proof. Let ${\sigma }_{\mathrm{in},n}\left(S\right)$ be the distribution of sketches obtained by adding $t$, then $n-1$ uniformly random records of $T$ into $S$ (or, equivalently, ${\sigma }_{\mathrm{in},n}\left(S\right)=P_n\left[S_E=S|t\in E\right]$). Then the definition of $\epsilon$-sketch privacy gives that for every sketch $S$, ${\sigma }_{\mathrm{out},n}\left(S\right)\ge e^{-\epsilon }{\sigma }_{\mathrm{in},n}\left(S\right)$. So we can express ${\sigma }_{\mathrm{out},n}$ as the sum of two distributions:

$${\sigma }_{\mathrm{out},n}=e^{-\epsilon }{\sigma }_{\mathrm{in},n}+\left(1-e^{-\epsilon }\right)\varsigma$$

for a certain distribution $\varsigma$.

First, we show that ${\sigma }_{\mathrm{out},\mathrm{kn}}={\left({\sigma }_{\mathrm{out},n}\right)}^k\cdot \sigma$ for a certain distribution $\sigma$. Indeed, to generate a sketch of cardinality $\mathrm{kn}$ that does not contain $t$ uniformly randomly, one can use the following process.

1.

Generate $k$ random sketches of cardinality $n$ which do not contain $t$, and merge them.

2.

For all $E\subseteq T$, denote by $p_E$ the probability that the $k$ sketches were generated with the records in $E$. There might be “collisions” between the $k$ sketches: if several sketches were generated using the same record, $\left|E\right|<\mathrm{kn}$. When this happens, we need to “correct” the distribution, and add additional records. Enumerating all the options, we denote $\sigma =\sum p_E{\sigma }_{E,\mathrm{nk}}^{\text{c}}$, where ${\sigma }_{E,\mathrm{nk}}^{\text{c}}$ is obtained by adding $\mathrm{nk}-\left|E\right|$ uniformly random records in $T\setminus E$ to $S_{\text{∅}}$. Thus, ${\sigma }_{\mathrm{out},\mathrm{kn}}={\left({\sigma }_{\mathrm{out},n}\right)}^k\cdot \sigma$.

Note that these distributions are in $V$: we can write ${\sigma }_{\mathrm{out},n}={\mathrm{avg}}_{E\in P_n\left(T\right),t\notin E}{\sigma }_E$, and similarly for ${\sigma }_{\mathrm{in},n}={\mathrm{avg}}_{E\in P_n\left(T\right)T,t\in E}{\sigma }_E$, as well as $\varsigma ={\left(1-e^{-\epsilon }\right)}^{-1}\left({\sigma }_{\mathrm{out},n}-e^{-\epsilon }{\sigma }_{\mathrm{in},n}\right)$, etc. Thus:

$$\begin{array}{cccc}{\sigma }_{\mathrm{out},\mathrm{kn}}& ={\left({\sigma }_{\mathrm{out},n}\right)}^k\cdot \sigma & & \\ & ={\left(e^{-\epsilon }{\sigma }_{\mathrm{in},n}+\left(1-e^{-\epsilon }\right)\varsigma \right)}^k\cdot \sigma & & \\ & =\sum _{i=0}^k\left(\frac{k}{i}\right)e^{-i\cdot \epsilon }{\left(1-e^{-\epsilon }\right)}^{k-i}{\sigma }_{\mathrm{in},n}^i\cdot {\varsigma }^{k-i}\cdot \sigma .& & \end{array}$$

Denoting $\alpha ={\sum }_{i=1}^k\left(\frac{k}{i}\right)e^{-i\cdot \epsilon }{\left(1-e^{-\epsilon }\right)}^{k-i}{\sigma }_{\mathrm{in},n}^{i-1}\cdot {\varsigma }^{k-i}\cdot \sigma$ and $\beta ={\varsigma }^k\cdot \sigma$, this gives us:

$${\sigma }_{\mathrm{out},\mathrm{kn}}=\alpha \cdot {\sigma }_{\mathrm{in},n}+{\left(1-e^{-\epsilon }\right)}^k\beta .$$

Finally, we can compute $\mathrm{add}\left({\sigma }_{\mathrm{out},\mathrm{kn}},t\right)$:

$$\begin{array}{cccc}\mathrm{add}\left({\sigma }_{\mathrm{out},\mathrm{kn}},t\right)& =\alpha \cdot {\sigma }_{\mathrm{in},n}\cdot {\sigma }_{\left\{t\right\}}+{\left(1-e^{-\epsilon }\right)}^k\beta \cdot {\sigma }_{\left\{t\right\}}& & \\ & =\alpha \cdot {\sigma }_{\mathrm{in},n}+{\left(1-e^{-\epsilon }\right)}^k\beta \cdot {\sigma }_{\left\{t\right\}}& & \end{array}$$

Note that since ${\sigma }_{\mathrm{in},n}={\mathrm{avg}}_{E\in P_n\left(T\right),t\in E}{\sigma }_E$, we have ${\sigma }_{\mathrm{in},n}\cdot {\sigma }_{\left\{t\right\}}={\sigma }_{\mathrm{in},n}$ by idempotence, and:

$$\begin{array}{cccc}\upsilon & \left({\sigma }_{\mathrm{out},\mathrm{kn}},\mathrm{add}\left({\sigma }_{\mathrm{out},\mathrm{kn}},t\right)\right)& & \\ & =\frac{1}{2}{\parallel {\sigma }_{\mathrm{out},\mathrm{kn}}-\mathrm{add}\left({\sigma }_{\mathrm{out},\mathrm{kn}},t\right)\parallel }_1& & \\ & =\frac{1}{2}{\Vert {\left(1-e^{-\epsilon }\right)}^k\beta -{\left(1-e^{-\epsilon }\right)}^k\beta \cdot {\sigma }_{\left\{t\right\}}\Vert }_1& & \\ & \le \frac{{\left(1-e^{-\epsilon }\right)}^k}{2}\left({\parallel \beta \parallel }_1+{\Vert \beta \cdot {\sigma }_{\left\{t\right\}}\Vert }_1\right)& & \\ & \le {\left(1-e^{-\epsilon }\right)}^k.& & \end{array}$$ □