# Sensitivity Estimation for Differentially Private Query Processing
## 4 Sensitivity Estimation for Join Queries
### Sampling-Based Sensitivity Estimation
#### 4.2.1. Estimation for One Residual Query
: By assuming the largest group \(j\
otin G_{terminate}\), then there exists a group \(k\), the lower bound of which is higher than the upper bound of group \(j\), i.e., \(C_{j}+\tau<C_{k}-\tau\), according to Algorithm 2 (line 14). Since \(|C_{i}-\mu_{i}|\leq\tau\) holds for every \(1\leq m\leq N\),  
\[\mu_{j}\leq C_{j}+\tau<C_{k}-\tau\leq\mu_{k} \tag{11}\]  
As \(\mu_{j}<\mu_{k}\), \(j\) is not the largest group, and this contradicts the assumption; thus, the assumption is not true. Second step. We use Theorem 3 to prove that the probability that the true result is larger than the output of the algorithm is limited. **Lemma 1**. : _Hoeffding Inequality [41]. Let \(Y=y_{1},y_{2}\ldots y_{N}\) be a set of \(N\) values in [0, 1] with an average value \(\frac{1}{N}\sum_{i=1}^{N}y_{i}=\mu\). Let \(X_{1},\ldots,X_{m}\) be a sequence of random variables drawn from \(Y\) without replacement. For every \(1\leq g\leq N\) and \(\epsilon>0\),_  
\[\Pr[\max_{g\leq m\leq N-1}(\frac{\sum_{i=1}^{m}X_{i}}{m}-\mu)\geq\tau]\leq \exp(-2g\tau^{2}) \tag{12}\]  
Suppose \(J\) is the total join size of \(\{\aleph_{i\in E}R_{i}\}\), we divide the join size for each group \(C_{i}\) by \(J\) to make each \(\frac{C_{i}}{J}\in[0,1]\). Thus, we can use the above inequality to obtain the error bound for each group. **Theorem 3**. : _For the join size in all the groups in \(G\), and for all the rounds in Algorithm 1, we have \(\Pr[\exists i,m,1\leq i\leq g,1\leq m\leq m_{i}:(est_{i,m}-\mu_{i})\geq l_{up} \cdot\tau]\leq\eta\), where \(\tau=\sqrt{\frac{2\log\log(m)+\log((g+1)\pi^{2}/6\eta)}{2m}}\), and \(J_{up}=l_{est}+\sqrt{\frac{2\log\log(n)+\log((g+1)\pi^{2}/6\eta)}{2m}}\). Here, \(m\) is the number of samples to estimate each group size, and \(n\) is the number of samples to estimate the total join size._  
Proof. : We prove the theorem in a similar way by using Theorem 3.2 in IFOCUS [40]; the difference is that we only need to prove that the probability that the estimate beyond the upper bound of the confidence interval is limited. We use the above lemma to compute the upper bound for each group as follows. \[\tau_{i}=\sqrt{\frac{(2\log\log(m)+\log(\pi^{2}/6\eta_{i}))}{2m}} \tag{13}\]  
\[\text{Then, }\Pr[\exists m,1\leq m\leq N:(\frac{\sum_{i=1}^{m}X_{i}}{m}-\mu)> \tau]\leq\eta_{i}.\]  
\[\Pr[\exists m,1\leq m\leq N:(\frac{\sum_{i=1}^{m}X_{i}}{m}-\mu)>\tau_{m}]\leq \sum_{r=1}\Pr[\exists m,\kappa^{r-1}\leq m\leq\kappa^{r}:(\frac{\sum_{i=1}^{m }X_{i}}{m}-\mu)>\tau_{m}]\]  
\[\leq\sum_{r=1}\Pr[\max_{\kappa^{r-1}\leq m\leq N-1}(\frac{\sum_{i=1}^{m}X_{i }}{m}-\mu)>\tau_{\kappa^{r}}] \tag{14}\]  
According to Lemma 1,  
\[\Pr[\max_{\kappa^{r-1}\leq m\leq N-1}(\frac{\sum_{i=1}^{m}X_{i}}{m}-\mu)>\tau _{\kappa^{r}}]\leq\frac{6\eta}{\pi^{2}r^{2}}. \tag{15}\]  
As \(\sum_{r\geq 1}\frac{1}{r^{2}}=\frac{\pi^{2}}{6}\),  
\[\sum_{r=1}\Pr[\max_{\kappa^{r-1}\leq m\leq N-1}(\frac{\sum_{i=1}^{m}X_{i}}{m}- \mu)>\tau_{\kappa^{r}}]\leq\eta \tag{16}\]  
Equation (13) computes the half-width \(\tau_{i}\) of the confidence interval for the estimation of \(\frac{C_{i}}{N}\). We can easily multiply \(\tau_{i}\) by the total join size \(N=J\) to calculate the half-width of the confidence interval for \(C_{i}\). The join size \(J\) is unknown in advance, but it can also be estimated according to the random walks we pick in each round. Suppose we get \(n\) paths to estimate \(J\),  
Figure 3:0  
Then, \(\Pr[\exists n,1\leq n\leq N:|\frac{\sum_{i=1}^{m}X_{i}}{n}-\mu|>\tau_{n}]\leq\eta\). Regarding \(J_{up}\) as the upper bound for a big group including all the join results, we get \(g+1\) groups. Suppose \(\eta_{i}=\eta_{j}\) for each pair \(i,j\in\{0,1,\ldots,g+1\}\); then, we get\(\eta_{i}=\eta/(g+1)\). By setting \(\eta\) in Equations (13) and (17) as \(\eta/(g+1)\), we get the \(\tau\) in line \(11\) of Algorithm 2. As many groups are removed once the upper bound of their estimates is below the lower bound of the largest group, the sample complexity for each group is different. We use the following theorem to prove the sample complexity of our algorithm. **Theorem 4**.