Graph-based modelling of query sets for differential privacy

Basit Öğe Kaydı
dc.contributor.authorInan, Ali
dc.contributor.authorGursoy, Mehmet Emre
dc.contributor.authorEsmerdag, Emir
dc.contributor.authorSaygin, Yucel
dc.date.accessioned2025-01-06T17:37:29Z
dc.date.available2025-01-06T17:37:29Z
dc.date.issued2016
dc.description28th International Conference on Scientific and Statistical Database Management (SSDBM) -- JUL 18-20, 2016 -- Budapest, HUNGARY
dc.description.abstractDifferential 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.
dc.description.sponsorshipHungarian Acad Sci, Wigner Res Ctr Phys
dc.description.sponsorshipScientific and Technological Research Council of Turkey (TUBITAK) [114E261]
dc.description.sponsorshipThis research was funded by The Scientific and Technological Research Council of Turkey (TUBITAK) under grant number 114E261.
dc.identifier.doi10.1145/2949689.2949695
dc.identifier.isbn978-1-4503-4215-5
dc.identifier.scopus2-s2.0-84982157005
dc.identifier.scopusquality0
dc.identifier.urihttps://doi.org/10.1145/2949689.2949695
dc.identifier.urihttps://hdl.handle.net/20.500.14669/2235
dc.identifier.wosWOS:000694698100003
dc.identifier.wosqualityN/A
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherAssoc Computing Machinery
dc.relation.ispartof28th International Conference on Scientific and Statistical Database Management (Ssdbm) 2016)
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/closedAccess
dc.snmzKA_20241211
dc.subjectDifferential privacy
dc.subjectmaximum clique problem
dc.subjectstatistical database security
dc.subjectSQL
dc.subjectrange queries
dc.titleGraph-based modelling of query sets for differential privacy
dc.typeConference Object

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu