# Sensitivity Estimation for Differentially Private Query Processing
## 1 Introduction  
In modern data-driven applications, join operations are widely used in areas ranging from social networking analysis [1, 2] to healthcare information management [3, 4], enabling the combination of datasets to reveal valuable insights and facilitate decision-making. However, this widespread use also introduces significant privacy risks. Sensitive information, such as personal records, can be exposed through vulnerabilities in third-party servers [5, 6], leading to potential misuse and violations of individual privacy. As a robust framework for privacy-preserving data analysis, differential privacy (DP) [7] introduces controlled noise to query results, ensuring that individual data contributions remain indistinguishable, thereby safeguarding data privacy. Usually, the noise is determined by the _sensitivity_[8], defined as the maximum difference in query results between two datasets differing by one record. Traditional sensitivity measures, such as global sensitivity, are easily applied to single-table queries, and the refined versions, such as local sensitivity and smooth sensitivity [9], are similarly applicable. However, for join queries, these methods prove inadequate, as they either introduce unbounded sensitivity or result in prohibitively intensive computation. Recent studies have proposed elastic sensitivity (ES) [10] and residual sensitivity (RS) [11] based on the upper bound of local sensitivity to achieve optimal performance inspecific settings, but these methods still have certain limitations. First, residual sensitivity suffers from computational inefficiency when processing large-scale complex join queries. Second, since elastic sensitivity always considers the worst case, it tends to overestimate sensitivity, resulting in degraded data utility. Existing work lacks a sensitivity calculation method that balances efficiency and utility. Therefore, this paper will investigate this aspect to address the challenges. Our observation is that the query sensitivity is typically computed based on certain database statistics, with more accurate sensitivity requiring increasingly complex and time-consuming statistical calculations. To tackle this problem, we raise the idea of using approximate query processing (AQP) methods to estimate query sensitivity. We present a sensitivity estimation framework, as illustrated in Figure 1. While we focus specifically on sensitivity estimation for multi-way join queries in this study, this core idea can be extended to a wide range of query types. To address the efficiency issue in the calculation of residual sensitivity. We propose _Sampling-SE_, which approximates the maximum boundary of each residual query using a sampling-based method, _RQE_. Specifically, it estimates the frequencies of the maximum groups in the residual queries of a multi-join query via random walks. To address the utility issue in the use of elastic sensitivity, we propose _Sketch-SE_ with _sketching sensitivity_, which is defined based on the AGMS sketch [12]. Since sketches for the relations involved in join queries are constructed offline, they can be used to efficiently estimate sensitivity when a query arrives. The main contributions of this paper are as follows:  
* We present a sampling-based sensitivity estimation method called _Sampling-SE_ for differentially private join query processing, which improves the efficiency of calculating residual sensitivity while remaining comparable in terms of accuracy;
* We also present a sketch-based method called _Sketch-SE_ using _sketching sensitivity_, which improves the utility of elastic sensitivity while remaining highly efficient;
* Experimental results on real-world and benchmark datasets show that our proposed methods obtain better performance than the traditional implementation of RS and ES. The remainder of the paper is organized as follows. We review the related work in Section 2. In Section 3, we introduce the preliminaries of differential privacy and the existing definitions of sensitivity.