Graph-based modelling of query sets for differential privacy

İnan, Ali and Gürsoy, Mehmet Emre and Esmerdağ, Emir and Saygın, Yücel (2016) Graph-based modelling of query sets for differential privacy. In: 28th International Conference on Scientific and Statistical Database Management (SSDBM 2016), Budapest, Hungary

[thumbnail of ssdbm.pdf] PDF

Download (462kB)


Differential privacy has gained attention from the community as the mechanism for privacy protection. Significant effort has focused on its application to data analysis, where statistical queries are submitted in batch and answers to these queries are perturbed with noise. The magnitude of this noise depends on the privacy parameter " and the sensitivity of the query set. However, computing the sensitivity is known to be NP-hard. In this study, we propose a method that approximates the sensitivity of a query set. Our solution builds a query-region- intersection graph. We prove that computing the maximum clique size of this graph is equivalent to bounding the sensitivity from above. Our bounds, to the best of our knowledge, are the tightest known in the literature. Our solution currently supports a limited but expressive subset of SQL queries (i.e., range queries), and almost all popular aggregate functions directly (except AVERAGE). Experimental results show the efficiency of our approach: even for large query sets (e.g., more than 2K queries over 5 attributes), by utilizing a state-of-the-art solution for the maximum clique problem, we can approximate sensitivity in under a minute.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: database security; Differential privacy; maximum clique problem; range queries; SQL; statistical
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Yücel Saygın
Date Deposited: 13 Nov 2016 17:37
Last Modified: 26 Apr 2022 09:23

Actions (login required)

View Item
View Item