# Comparative Analysis of Local Differential Privacy Schemes in Healthcare Datasets
## 2 Preliminaries
### LOPUB Scheme
#### 2.5.1 Bloom Filters  
Encoding user information involves representing user input using a Bloom filter \(\mathcal{H}\)([PERSON], 2018; [PERSON], 2018), a probabilistic data structure designed by [PERSON] in 1970 Bloom ([PERSON], 2018) to test membership in a set. Consider a dataset \(U\) with \(N\) users, where the data record \(u^{i}\) for the \(i\)th user comprises \(d\) attributes, denoted as \(\mathbf{u^{i}}=[u^{i}_{j},\ldots,u^{i}_{d}]\). To encode each \(u^{i}_{j}\), the user utilizes a Bloom filter with a set \(\mathcal{H}\) of hash functions designed for \(U_{j}\), where \(U_{j}\) represents the \(j\)th attribute of \(U\). Specifically, the user applies \(h_{j}\) hash functions \(\mathcal{H}_{j,1},\ldots,\mathcal{H}_{j,h_{j}}\) from \(\mathcal{H}_{j}\) to map \(u^{i}_{j}\) to a length-\(m_{j}\) bit string \(s^{i}_{j}\), where \(m_{j}\) is the length of the Bloom filter and \(1\leq j\leq d\). Consequently, \(u^{i}_{j}\) is inserted into a \(m_{j}\)-bit Bloom filter using \(h\) hash functions from \(\mathcal{H}\), represented as \(H_{j}(\Omega)\), with \(s^{i}_{j}[b]\) denoting the \(b\)th bit of the bit string \(s^{i}_{j}\). The length of the Bloom filter \(m_{j}\) for \(U_{j}\) is computed as  
\[m_{j}=\frac{\ln\frac{1}{p}}{(\ln 2)^{2}}|\Omega_{j}|. \tag{3}\]  
Here, \(|\Omega_{j}|\) denotes the cardinality of attribute \(U_{j}\), and \(p\) represents the false-positive probability. The number of hash functions used in a Bloom filter directly impacts the likelihood of false positives. Employing a greater number of hash functions decreases the probability of collisions, thereby enhancing the filter's precision. \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Description** \\ \hline \(k\) & dimensionality of joint probability distribution estimation \\ \(U\) & dataset \\ \(N\) & number of users \\ \(U^{i}\) & \(i\)th user \\ \(d\) & number of attributes in \(U\) \\ \(U_{j}\) & /th attribute in \(U\) \\ \(u^{i}_{j}\) & value of \(i\)th user with attribute \(j\)th in \(U\) \\ \(\Omega_{j}\) & domain of \(U_{j}\) \\ \(\mathcal{H}\) & set of hash functions \\ \(p\) & false-positive probability used to calculate \(m_{j}\) \\ \(m_{j}\) & length of \(s^{i}_{j}\) \\ \(s^{i}_{j}\) & bloom filter of \(u^{i}_{j}\), \(s^{i}_{j}=\mathcal{H}_{j}(u^{i}_{j})\) \\ \(s^{i}_{j}[b]\) & \(b\)th bit of \(s^{i}_{j}\) \\ \(s^{i}_{j}\) & randomized bloom filter of \(u^{i}_{j}\) \\ \(s^{i}_{j}[b]\) & \(b\)th bit of \(s^{i}_{j}[b]\) \\ \(\hat{y}\) & counts the number of 1’s in \(s^{i}_{j}\) \\ \(\hat{y}[b]\) & \(b\)th bit of \(\hat{y}[b]\) \\ \(y\) & original count \\ \(y[b]\) & \(b\)th bit of \(y\) \\ \(M\) & candidate bit matrix \\ \(\hat{R}\) & Pearson correlation coefficient matrix \\ \(F_{j}\) & marginal distribution function of \(U_{j}\) \\ \(F_{j}^{-1}\) & inverse cumulative distribution function of \(U_{j}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Notations. Next, let us discuss how the size of \(m_{j}\) impacts the error rate. The probability of not setting a bit by \(h\) hash functions becomes \(p=\left(1-\frac{1}{m_{j}}\right)^{h}\). For \(\eta\) elements mapped-in, it becomes \(p=\left(1-\frac{1}{m_{j}}\right)^{h\eta}\). Now our interest lies in setting a bit by mistake for a string, resulting in a false positive and thus an error rate. The probability is computed as \(p=1-\left(1-\frac{1}{m_{j}}\right)^{h\eta}\). Then, we need to repeat this process \(h\) times. Finally, the error rate for a string is computed as \(p=\left(1-\left(1-\frac{1}{m_{j}}\right)^{h\eta}\right)^{h}\). In the context of this scenario, as the number of bits \(m_{j}\) approaches infinity, the error rate diminishes to \(0\), indicating an increasingly accurate result. Conversely, when \(m_{j}\) is set to \(1\), the error rate rises to \(1\), signifying a \(100\%\) error rate, implying that every attempt at hashing results in a false positive, rendering the outcome entirely inaccurate.