# 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  
Calculating the true result of the maximum boundary of each residual query is costly. To this end, we present a sampling-based sensitivity estimation method (Sampling-SE). Inspired by \"Wander-Join\" [28], we start the algorithm by sampling the join path of each group in a round-robin fashion. In order to make sure all the groups are well estimated, \"Wander-Join\" iteratively selects the group that has the largest confidence interval to start the next random walk. Unlike this, we do not care about all the groups; we only care about the largest group. To address this, we adopt an idea similar to \"iFOCUS\" [40] where we sample more for the groups we care about. The difference is that \"iFOCUS\" keeps removing the groups that have no overlapping confidence interval with others for ordering guarantee, whereas we keep removing the group for which the confidence interval has no overlap with the largest group. The pseudo-code of the Sampling-SE algorithm is shown in Algorithm 1. As computing the \(T_{E}\) for each residual query of a multi-join query is costly, we use a sampling-based method \(RQE\) to estimate the maximum boundary \(T_{E}\) of each residual query \(q_{E}\). ```
0: Multi-Join query \(q\)
0: The sensitivity of \(q\)
1:for Each residual query \(q_{E}\) of \(q\)do
2:\(T_{E}\gets RQE(q_{E})\)
3:endfor
4: Compute the sensitivity based on \(T_{E}\) for each \(q_{E}\) according to Definition 6. ```  
**Algorithm 1** Sampling-SE  
Details of the residual query estimation (RQE) method are shown in Algorithm 2. To better illustrate the algorithm's workflow, we have added a flowchart for clarification in Figure 3. The algorithm first conducts \(m\) join paths for each group according to the random walk, and we initialize the estimation \(C_{1},C_{2},\ldots,C_{g}\) for each group in \(G=\{1,2,\ldots,g\}\) (line 1). We then estimate the join size \(J\) and half-width of the confidence interval \(\tau_{J}\) for the query \(q_{E}\). The main part of this algorithm (lines 3-18) iteratively increases the sample size for each candidate large group, the confidence interval of which overlaps with the current largest group. For the candidate large groups in \(G\), the algorithm adds a random walk path to update the estimations (lines 6-12). The algorithm _Estimate_ computes the new estimate \(C_{i}\) and half-width of confidence interval \(\tau_{i}\) for the \(i\)-th group according to the join path \(p\) (line 9), and then it estimates the join size and the confidence interval for \(J\) in the same way (line 10). For the small groups whose confidence intervals have no overlap with the current largest group, we remove them from \(G\) (lines 13-17). The algorithm stops when the half-width of the confidence interval \(\tau\) is below \(\tau_{0}\), meaning that the estimation is accurate enough. Figure 3: Flowchart of algorithm RQE. Algorithm 3 estimates the result size \(C\) of a query \(q\) based on the join path \(p\), and it computes the half-width of confidence interval \(\tau\) according to Hoeffding Inequality [41]. We use two steps to prove that the output of the algorithm is a sufficiently accurate estimate for each \(T_{E}\): (1) the algorithm does not miss the largest group, and (2) the probability that the true largest group size is larger than the output of the algorithm is smaller than \(\eta\). ```
1:\(x\leftarrow\) Estimate \(|q|\) with path \(p\) according to WanderJoin. 2:\(C\leftarrow\frac{m-1}{m}C+\frac{1}{m}x\)
3:\(\tau=\sqrt{\frac{2\log\log(m)+\log((g+1)\pi^{2}/6\eta)}{2m}}\)
4:Return:\(C\), \(\tau\). ```  
**Algorithm 2** RQE  
First step. We use Theorem 2 to prove that the algorithm does not miss the largest group. **Theorem 2**. : _If for each group \(i\), we have \(|C_{i}-\mu_{i}|\leq\tau\) for every \(1\leq m\leq N\), then the largest group is \(j\in G\) at termination time._  
Proof.