# Sensitivity Estimation for Differentially Private Query Processing
## 2 Related Works  
Differential Privacy [7] is a mathematical framework aiming at quantifying and managing privacy risks. It is widely used in the field of privacy-preserving data releasing [13,14] and mining [15,16], machine learning [17,18], and social network analysis [19]. Differential privacy can be easily applied to protect the privacy of query processing by adding noise  
Figure 1: Framework of differentially private query processing with AQP.  
correlated to the sensitivity into the query results [8], gaining traction in many real-world applications [20; 21].  
Computing the sensitivity of join queries is challenging. Recently, several mechanisms supporting join queries have been proposed, such as Privacy Integrated Queries (PINQs) [22] and its weighted version wPINQ [23], but both of these are based on global sensitivity, which means that the sensitivity could be extremely large, thus resulting in low utility. [PERSON] et al. [9] propose local sensitivity to fix one of two datasets that are adjacent to the actual dataset being queried and take into account all its neighbors. However, it does not meet the requirements of differential privacy. Smooth sensitivity [9] is the tightest smooth upper bound of local sensitivity that can prevent the privacy leakage caused by the mutation of local sensitivity, but its computation complexity is _Non-deterministic Polynomial-time hard_ (NP-hard). Elastic sensitivity (ES) [10] and residual sensitivity (RS) [11] are both based on the idea of finding the smooth upper bound of the local sensitivity. ES is computed based on the maximum frequency of the join values in each relation, and RS is computed based on some residual queries of a multi-join query.  
Approximate query processing (AQP) is a technique that can be used to estimate join sizes efficiently [24]. Sampling [25; 26] the join result is one of the AQP methods that has high performance. Ripple join [27] and wander join [28] are online aggregations that can be used for queries with join operators. [PERSON] et al. [29] revisited this issue to integrate the previous approaches into a universal framework that contains two main phases: calculating the upper bound of the join size weight and then sampling from the joins. Moreover, there are other techniques, such as histograms [30; 31], that are leveraged to estimate the size of join query results. AQP presents a viable solution for efficient and private data analysis [32; 33], particularly when exact query answers cannot be obtained under DP constraints. Sketches are probabilistic data structures used for stream summarization tasks, and masses of sketches, such as AGMS [12; 34], Count-sketches [35], and Count-Min sketches [36], are proposed for frequency estimation, heavy hitter mining, join size estimation, etc. AGMS sketch is designed for self-join estimation, which can also be used to estimate the join size of multi-join queries, including condition filters [37]. [PERSON] et al. [38] introduce a join size estimation framework under LDP based on FAGMS sketch [39].  
Although a variety of definitions for sensitivity are proposed for join queries, they all have some shortcomings. Global sensitivity is unbounded for multi-join queries, and local sensitivity does not satisfy the differential privacy. The computation of smooth sensitivity is NP-hard. ES is easy to compute but has poor accuracy. RS is more accurate but more time-consuming. No existing studies have made efforts toward adopting AQP methods for sensitivity estimation. However, AQP methods such as sampling and sketches cannot be simply adopted to reduce the cost. This is because the sensitivity of a multi-join query depends on many statistics, as shown in RS, and individually estimating each statistic is still costly. Therefore, we propose a sampling-based sensitivity estimation method to focus on estimating the statistics and how this contributes to the sensitivity. We also propose a sketch-based method that constructs sketches for each relation offline and efficiently estimates the sensitivity online.