# Sensitivity Estimation for Differentially Private Query Processing
## 4 Sensitivity Estimation for Join Queries
### Sketch-Based Sensitivity Estimation
#### 4.3.2 Sketching Sensitivity for Multi-Join Queries  
We define the _sketching sensitivity_ of a multi-join query in terms of \(sk^{(k)}(R_{i})\), which is a sketch of the relation \(R_{i}\) at distance \(k\) from the database. We build a connection between local sensitivity and sketching sensitivity. We first consider estimating the local sensitivity based on sketches as follows:  
**Theorem 5**. : _Local sensitivity can be computed as_  
\[LS_{q}(I)=\max_{i\in P}\max_{v\in dom(JA(R_{i}))}(v\Join_{j\in[r]-\{i\}}R_{j, l}), \tag{22}\]  
_where \(R_{j,l}\) is the jth relation in instance \(I\)._  
According to the following theorem proved in reference [12], the relative error of the join-size-estimate-based sketches can be limited. **Theorem 6**. : _Let \(Q\) be an acyclic, multi-join query over relations \(R_{1},\ldots R_{r}\), such that \(Count(Q)\geq L\) and Self-Join(\(sk_{k}\))\(\leq U_{k}\). Then, using a sketch of size \(O(\frac{2^{2n}(\prod_{k=1}^{2}U_{k})log(1/\eta)}{L^{2}\tau^{2}}\sum_{j=1}^{n} \log|dom(A_{j})|)\), it is possible to approximate \(Count(Q)\) so that the relative error of the estimate is at most \(\tau\) with a probability of at least \(1-\eta\)._We compute the upper bound of the join size by dividing the estimate by \((1-\tau)\); thus, with the probability of at least \(1-\eta\), the true join size is \(J<\frac{est}{1-\tau}\). Each \(\
u\
w_{j\in[n]-\{i\}}\;R_{j,I}\) in Equation (22) can be estimated based on the sketch of each relation:  
\[ \begin{split}&(\
u\
w_{j\in[n]-\{i\}}\;R_{j})\leq\frac{\mean{ \sum\limits_{s\in[1,s]}\left(\prod\limits_{l\in IA(R_{i,l})}\xi_{l,s}(\
u) \cdot\prod\
olimits_{j\in[n]-\{i\}}sk_{s}(R_{j,I})\right)}}{1-\tau}\\ &\leq\frac{\mean{\sum\limits_{s\in[1,s]}\left|\prod\
olimits_{j \in[n]-\{i\}}sk_{s}(R_{j,I})\right|}}{1-\tau}\end{split}  \tag{23}\]  
with a probability of at least \(1-\eta\). The second inequality of Equation (23) holds because \(\prod\limits_{l\in IA(R_{i,l})}\xi_{l,s}(\
u)\in\{-1,1\}\). Since the smooth upper bound of the local sensitivity is defined based on the local sensitivity at distance \(k\), we also consider estimating it according to the sketches. Theorem 7 ([9]): _Suppose \(\mathcal{I}^{k}=\{I^{\prime}:d(I,I^{\prime})=k\}\) is the set of instances having distance \(k\) to \(I\); then, the local sensitivity at distance \(k\) can be computed as_  
\[LS^{(k)}_{q}(I)=\max\limits_{I^{\prime}\in\mathcal{I}^{k}}\max\limits_{i\in P }\max\limits_{v\in d\omega(\{A(R_{i})\})}(\
u\
w_{j\in[r]-\{i\}}\;R_{j,I^{ \prime}}) \tag{24}\]  
Let \(S^{k}=\{(k_{1},k_{2},\ldots,k_{r})|\sum k_{i}=k,k_{x\
otin P}=0)\}\) be the set of all the partitions of \(k\) tuples, where the \(LS^{(k)}_{q}(I)\) can be rewritten as follows:  
\[LS^{(k)}_{q}(I)=\max\limits_{(k_{1},k_{2},\ldots,k_{r})\in S^{k}}\max\limits_{ i\in P}\max\limits_{v\in d\omega(\{A(R_{i})\})}(\
u\
w_{j\in[r]-\{i\}}\;R^{(k_{j})}_{ j}) \tag{25}\]  
Each \(\
u\
w_{j\in[n]-\{i\}}\;R^{(k_{j})}_{j}\) can be estimated based on the sketch of each relation:  
\[ \begin{split}&(\
u\
w_{j\in[n]-\{i\}}\;R_{j})<=\frac{\mean{ \sum\limits_{s\in[1,s]}\left(\prod\limits_{l\in IA(R_{i})}\xi_{l,s}(\
u)\cdot \prod\
olimits_{j\in[n]-\{i\}}sk^{(k_{j})}_{s}(R_{j})\right)}}{1-\tau}\\ &<=\frac{\mean{\sum\limits_{s\in[1,s]}\left|\prod\
olimits_{j \in[n]-\{i\}}sk^{(k)}_{s}(R_{j})\right|}}{1-\tau}\end{split}  \tag{26}\]  
Therefore,  
\[LS^{(k)}_{q}(I)\leq\max\limits_{I^{\prime}\in\mathcal{I}^{k}}\max\limits_{i\in P }\frac{\mean{\sum\limits_{s\in[1,s]}\left|\prod\
olimits_{j\in[n]-\{i\}}sk^{( k)}_{s}(R_{j})\right|}}{1-\tau} \tag{27}\]  
We can regard the right-side of the above equation as the upper bound for \(LS^{(k)}_{q}(I)\), and we define the sketch sensitivity as follows:  
Theorem 8 ([42]): _Let \(Q=R_{1}\bowtie\ldots\bowtie R_{k}\) be a \(k\)-way join query.