Cormode, Graham, Kulkarni, Tejas M. and Srivastava, D. (2018) Constrained private mechanisms for count data. In: 34th IEEE International Conference on Data Engineering, Paris, France, 16–19 Apr 2018. Published in: IEEE Transactions on Knowledge and Data Engineering doi:10.1109/TKDE.2019.2912179 ISSN 1041-4347.
![[thumbnail of WRAP-constrained-private-mechanisms-count-data-Cormode-2018.pdf]](https://cdn.statically.io/img/wrap.warwick.ac.uk/101737/1.hassmallThumbnailVersion/WRAP-constrained-private-mechanisms-count-data-Cormode-2018.pdf)  Preview |
PDF
WRAP-constrained-private-mechanisms-count-data-Cormode-2018.pdf - Accepted Version - Requires a PDF viewer. Download (2MB) | Preview |
Abstract
Concern about how to aggregate sensitive user data without compromising individual privacy is a major barrier to greater availability of data. Differential privacy has emerged as an accepted model to release sensitive information while giving a statistical guarantee for privacy. Many different algorithms are possible to address different target functions. We focus on the core problem of count queries, and seek to design mechanisms to release data associated with a group of n individuals. Prior work has focused on designing mechanisms by raw optimization of a loss function, without regard to the consequences on the results. This can leads to mechanisms with undesirable properties, such as never reporting some outputs (gaps), and overreporting others (spikes). We tame these pathological behaviors by introducing a set of desirable properties that mechanisms can obey. Any combination of these can be satisfied by solving a linear program (LP) which minimizes a cost function, with constraints enforcing the properties. We focus on a particular cost function, and provide explicit constructions that are optimal for certain combinations of properties, and show a closed form for their cost. In the end, there are only a handful of distinct optimal mechanisms to choose between: one is the well-known (truncated) geometric mechanism; the second a novel mechanism that we introduce here, and the remainder are found as the solution to particular LPs. These all avoid the bad behaviors we identify. We demonstrate in a set of experiments on real and synthetic data which is preferable in practice, for different combinations of data distributions, constraints, and privacy parameters.
| Item Type: | Conference Item (Paper) |
|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Journal or Publication Title: | IEEE Transactions on Knowledge and Data Engineering |
| Publisher: | IEEE Computer Society |
| ISSN: | 1041-4347 |
| Official Date: | 27 February 2018 |
| Dates: | Date Event 27 February 2018 Accepted |
| DOI: | 10.1109/TKDE.2019.2912179 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Open Access (Creative Commons open licence) |
| Date of first compliant deposit: | 2 May 2018 |
| Date of first compliant Open Access: | 2 May 2018 |
| Funder: | This work is supported in part by The Alan Turing Institute under the EPSRC grant EP/N510129/1, Marie Curie Career Integration Grant 618202, an AT&T Labs VURI award, and a Warwick Collaborative Postgraduate Research Scholarship |
| RIOXX Funder/Project Grant: | Project/Grant ID RIOXX Funder Name Funder ID EP/N510129/1 [EPSRC] Engineering and Physical Sciences Research Council 618202 Marie Curie Career Integration Grant UNSPECIFIED UNSPECIFIED AT&T Labs VURI award UNSPECIFIED UNSPECIFIED Warwick Collaborative Postgraduate Research Scholarship UNSPECIFIED |
| Conference Paper Type: | Paper |
| Title of Event: | 34th IEEE International Conference on Data Engineering |
| Type of Event: | Conference |
| Location of Event: | Paris, France |
| Date(s) of Event: | 16–19 Apr 2018 |
| Related URLs: | |
| Persistent URL: | https://wrap.warwick.ac.uk/101737/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |