title   
  

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

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
451Kb

Official URL: http://dx.doi.org/10.1145/2949689.2949695

Abstract

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
Subjects:UNSPECIFIED
ID Code:29683
Deposited By:Yücel Saygın
Deposited On:13 Nov 2016 17:37
Last Modified:13 Nov 2016 17:37

Repository Staff Only: item control page