# Sensitivity Estimation for Differentially Private Query Processing
## 3 Preliminaries
### Sensitivity  
Sensitivity measures the maximum change in the query result when inserting or deleting a record. In this section, we introduce five different definitions of sensitivity. Global sensitivity calculates the maximum difference of the query result on two neighboring databases, i.e., \(d(I,I^{\prime})=1\).  
**Definition 2**.: _Global sensitivity (GS) [8]. For \(q:D^{n}\to R^{d}\) and all \(I,I^{\prime}\in D^{n}\), the GS of \(q\) is_  
\[GS_{q}=\max_{I,I^{\prime}:d(I,I^{\prime})=1}||q(I)-q(I^{\prime})|| \tag{2}\]  
Local sensitivity is defined similarly, but computed for a fixed database.  
**Definition 3**.: _Local sensitivity (LS) [9]. For \(q:D^{n}\to R^{d}\) and \(I^{\prime}\in D^{n}\), the LS for \(I\) is_  
\[LS_{q}(I)=\max_{I^{\prime}:d(I,I^{\prime})=1}||q(I)-q(I^{\prime})|| \tag{3}\]  
However, local sensitivity poses privacy risks. To address this, smooth sensitivity is proposed to compute a smooth upper bound on local sensitivity.  
**Definition 4**.: _Smooth sensitivity [9]. Smooth sensitivity is defined based on the generalization of the local sensitivity of \(f\) at distance \(k\),_  
\[LS^{k}_{q}(I)=\max_{I^{\prime}\in D^{n}:d(I,I^{\prime})=k}LS_{q}(I^{\prime}) \tag{4}\]  
_and the smooth sensitivity of \(q\) for \(I\) is_  
\[SS_{q}(I)=\max_{0\leq k\leq n}e^{-\beta k}LS^{k}_{q}(I),\beta=\frac{\epsilon}{ 2\ln 2/\delta} \tag{5}\]  
Computing smooth sensitivity is time-consuming, requiring exponential time for large datasets. To address this, elastic and residual sensitivities are proposed, both of which are smooth upper bounds of local sensitivity. [PERSON] et al. [9] proved that any smooth upper bound of local sensitivity can preserve privacy according to differential privacy.  
**Definition 5**.: _Elastic sensitivity [10]. The elastic sensitivity of a database 1 is defined based on the smooth upper bound of local sensitivity as follows._  
\[ES_{q}(I)=\max_{0\leq k\leq n}e^{-\beta k}\widetilde{LS}^{k}_{q}(I),\beta= \frac{\epsilon}{2\ln 2/\delta} \tag{6}\]_where \(\widetilde{LS}_{q}^{k}(I)\) is an upper bound of local sensitivity at distance \(k\),_  
\[\widetilde{LS}_{q}^{k}(I)=\max_{i\in P}(\prod_{j\in P-\{i\}}(mf(x_{j}\cap x_{p(j,i)},I_{j})+k)\cdot\prod_{j\in[n]-P}mf(x_{j}\cap x_{p(j,i)},I_{j})) \tag{7}\]  
\(mf(x,I_{j})\) _is the maximum frequency on attribute \(x\) in \(I_{j}\), and \(P\) is the private attribute set._  
Elastic sensitivity can be computed based on the maximum frequencies of the join attributes. However, it computes the maximum frequency of the multi-way join based on the assumption that all of the most frequent join attribute values can be joined with each other. So, elastic sensitivity involves many errors.  
**Definition 6**.: _Residual sensitivity [11]. The residual sensitivity of a database \(I\) is also defined based on the smooth upper bound of local sensitivity at distance \(k\),_  
\[RS_{q}(I)=\max_{0\leq k\leq n}e^{-\beta k}\min(G\mathbb{S}_{q},\widetilde{LS} _{q}^{k}(I)),\beta=\frac{\epsilon}{2\ln 2/\delta} \tag{8}\]  
_where \(\widetilde{LS}_{q}^{k}(I))\) is an upper bound of local sensitivity at distance \(k\),_  
\[\widetilde{LS}_{q}^{k}(I)=\max_{s\in\mathbb{S}^{k}}\max_{i\in P}\hat{T}_{[n]- \{i\},s}(I) \tag{9}\]  
\[\hat{T}_{E,s}(I)=\sum_{E^{\prime}\subseteq E}\left(T_{E-E^{\prime}}(I)\prod_{ i\in E^{\prime}}s_{i}\right) \tag{10}\]  
\(\hat{T}_{E,s}(I)\) _computes the maximum boundary for \(I^{\prime}:d(I,I^{\prime})=k\), and \(s\) is one way of partitioning \(k\) into different relations in \(E\)._  
Residual sensitivity requires computing the maximum boundaries of residual queries for each private relation. This involves solving a join-aggregate query with group-by conditions, which remains computationally expensive, especially for complex joins.