Sensitivity Estimation for Differentially Private Query Processing
Differential privacy is a robust framework for private data analysis and query processing, which achieves privacy preservation by introducing controlled noise to query results in a centralized setting. The sensitivity of a query, defined as the maximum change in query output resulting from the addit...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-07-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/15/14/7667 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849714772408270848 |
|---|---|
| author | Meifan Zhang Xin Liu Lihua Yin |
| author_facet | Meifan Zhang Xin Liu Lihua Yin |
| author_sort | Meifan Zhang |
| collection | DOAJ |
| description | Differential privacy is a robust framework for private data analysis and query processing, which achieves privacy preservation by introducing controlled noise to query results in a centralized setting. The sensitivity of a query, defined as the maximum change in query output resulting from the addition or removal of a single data record, directly influences the magnitude of noise to be introduced. Computing sensitivity for simple queries, such as count queries, is straightforward, but it becomes significantly more challenging for complex queries involving join operations. In such cases, the global sensitivity can be unbounded, which substantially impacts the accuracy of query results. While existing measures like elastic sensitivity and residual sensitivity provide upper bounds on local sensitivity to reduce noise, they often struggle with either low utility or high computational overhead when applied to complex join queries. In this paper, we propose two novel sensitivity estimation methods based on sampling and sketching techniques, which provide competitive utility while achieving higher efficiency compared to existing state-of-the-art approaches. Experiments on real-world and benchmark datasets confirm that both methods enable efficient differentially private joins, significantly enhancing the usability of online interactive query systems. |
| format | Article |
| id | doaj-art-e2d7869dee7b4e9a9998d14f6ec5af53 |
| institution | DOAJ |
| issn | 2076-3417 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj-art-e2d7869dee7b4e9a9998d14f6ec5af532025-08-20T03:13:36ZengMDPI AGApplied Sciences2076-34172025-07-011514766710.3390/app15147667Sensitivity Estimation for Differentially Private Query ProcessingMeifan Zhang0Xin Liu1Lihua Yin2Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 510006, ChinaCyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 510006, ChinaCyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 510006, ChinaDifferential privacy is a robust framework for private data analysis and query processing, which achieves privacy preservation by introducing controlled noise to query results in a centralized setting. The sensitivity of a query, defined as the maximum change in query output resulting from the addition or removal of a single data record, directly influences the magnitude of noise to be introduced. Computing sensitivity for simple queries, such as count queries, is straightforward, but it becomes significantly more challenging for complex queries involving join operations. In such cases, the global sensitivity can be unbounded, which substantially impacts the accuracy of query results. While existing measures like elastic sensitivity and residual sensitivity provide upper bounds on local sensitivity to reduce noise, they often struggle with either low utility or high computational overhead when applied to complex join queries. In this paper, we propose two novel sensitivity estimation methods based on sampling and sketching techniques, which provide competitive utility while achieving higher efficiency compared to existing state-of-the-art approaches. Experiments on real-world and benchmark datasets confirm that both methods enable efficient differentially private joins, significantly enhancing the usability of online interactive query systems.https://www.mdpi.com/2076-3417/15/14/7667differential privacysensitivityjoin queryapproximate query processing |
| spellingShingle | Meifan Zhang Xin Liu Lihua Yin Sensitivity Estimation for Differentially Private Query Processing Applied Sciences differential privacy sensitivity join query approximate query processing |
| title | Sensitivity Estimation for Differentially Private Query Processing |
| title_full | Sensitivity Estimation for Differentially Private Query Processing |
| title_fullStr | Sensitivity Estimation for Differentially Private Query Processing |
| title_full_unstemmed | Sensitivity Estimation for Differentially Private Query Processing |
| title_short | Sensitivity Estimation for Differentially Private Query Processing |
| title_sort | sensitivity estimation for differentially private query processing |
| topic | differential privacy sensitivity join query approximate query processing |
| url | https://www.mdpi.com/2076-3417/15/14/7667 |
| work_keys_str_mv | AT meifanzhang sensitivityestimationfordifferentiallyprivatequeryprocessing AT xinliu sensitivityestimationfordifferentiallyprivatequeryprocessing AT lihuayin sensitivityestimationfordifferentiallyprivatequeryprocessing |