Graph-based modelling of query sets for differential privacy
[ X ]
Tarih
2016
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Assoc Computing Machinery
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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 s 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.
Açıklama
28th International Conference on Scientific and Statistical Database Management (SSDBM) -- JUL 18-20, 2016 -- Budapest, HUNGARY
Anahtar Kelimeler
Differential privacy, maximum clique problem, statistical database security, SQL, range queries
Kaynak
28th International Conference on Scientific and Statistical Database Management (Ssdbm) 2016)
WoS Q Değeri
N/A
Scopus Q Değeri
0
