# Sensitivity Estimation for Differentially Private Query Processing
## 4 Sensitivity Estimation for Join Queries
### Sampling-Based Sensitivity Estimation
#### 4.2.2 Improved Sampling-Based Sensitivity Estimation  
In the previous section, we introduced the estimating algorithm for each residual query of a multi-way join query. However, computing the residual sensitivity requires calculating all the residual results in \(\{q_{E}|E\subseteq nr-\{i\},i\in P\}\). We can simply use Algorithm 2 to estimate each residual query, but it involves redundant samples. As shown in Figure 4, with a join path of \(a_{1}\to b_{1}\to c_{2}\), we can estimate \(|t(a_{1})\Join R_{1}\Join R_{2}\Join R_{3}|=\frac{1}{\frac{1}{3}\frac{1}{2}}=6\) and \(|t(b_{1})\Join R_{2}\Join R_{3}|=\frac{1}{2}=2\). Therefore, we propose an algorithm to reduce the sample complexity by leveraging each path to estimate the candidate of all the values on the path.  
The pseudo-code is shown in Algorithm 4. As the basic idea is to estimate the join size of each value on the path to reduce the sample complexity, we start the algorithm by  
Figure 4: Estimations of values on one join path.  
drawing samples for the residual query that have the most relations, because a long path can provide estimations for more values. The algorithm then draws new samples for the groups of \(q_{E}\) to update the estimations and confidence intervals for each \(E^{\prime}\subseteq E\) (lines 4-13). The algorithm iteratively removes the group from the group set \(G_{E}\) of each \(q_{E}\in ARQS\) if it is not the candidate largest group (lines 15-19), and it removes the \(q_{E}\) from \(ARQS\) once all the remaining groups of \(q_{E}\) are well estimated (lines 20-22). The algorithm stops once the active residual query set (\(ARQS\)) is empty.  
```
0: Multi-way Query \(q\), Residual queries \(RQS=\{q_{E}|E\subseteq[n]-\{i\},i\in P\}\), Terminal error bound \(\tau_{0}\)
0: The estimations \(\{T_{E}|q_{E}\in RQS\}\)
1:\(ARQS\gets RQS\)
2:while\(ARQS\
eq\emptyset\)do
3:\(q_{E}\leftarrow\arg\max_{q_{E}\in ARQS}|E|\)
4:for each group \(i\in G_{E}\)do
5: Conduct a random walk \(p\) starting from \(t(v_{i})\).
6:for each \(E^{\prime}\subseteq E\) on \(p\)do
7:\(m_{E^{\prime},i}\gets m_{E^{\prime},i}+1\)
8:\(n_{E^{\prime}}\gets n_{E^{\prime}}+1\)
9:\(C_{E^{\prime},i}\), \(\tau_{E^{\prime},i}\leftarrow\text{Estimate}(p,t(v_{i})\
sim q^{\prime}_{E},m, C_{E^{\prime},i})\)
10:\(J_{E^{\prime}}\), \(\tau_{I_{E^{\prime}}}\leftarrow\text{Estimate}(p,q_{E^{\prime}},n,J)\)
11:\(\tau_{E^{\prime},i}\leftarrow\tau_{E^{\prime},i}\cdot(J_{E^{\prime}}+\tau_{ I_{E^{\prime}}})\)
12:endfor
13:endfor
14:for each \(q_{E}\in ARQS\)do
15:for each \(i\in G_{E}\)do
16:if\(C_{E,i}+\tau_{E,i}<\max_{j\in G_{E}}(C_{E,j}-\tau_{E,j})\)then
17:\(G_{E}\gets G_{E}-\{i\}\)
18:endif
19:endfor
20:if\(\tau_{E,i}<=\tau_{0}\) for each group \(i\in G_{E}\)then
21:\(ARQS\gets ARQS-\{q_{E}\}\)
22:endif
23:endfor
24:endwhile
25:return:\(\{T_{E}=max_{i\in G_{E}}(C_{E,i}+\tau_{E,i})|q_{E}\in RQS\}\)
```  
**Algorithm 4** Improved-RQE  
In this algorithm, one join path can be used to estimate the join size of each value on the path. Thus, the sample complexity can be reduced.