On optimal differentially private mechanisms for count-range queries
Open Access
- 18 March 2013
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 2013, 261-271
Abstract
While there is a large and growing body of literature on differentially private mechanisms for answering various classes of queries, to the best of our knowledge “count-range” queries have not been studied. These are a natural class of queries that ask “is the number of rows in a relation satisfying a given predicate between two integers θ1 and θ2?” Such queries can be viewed as a simple form of SQL “having” queries. We begin by developing a provably optimal differentially private mechansim for count-range queries for a single consumer. For count queries (in contrast to count-range queries), Ghosh et al. [9] have provided a differentially private mechanism that simultaneously maximizes utility for multiple consumers. This raises the question of whether such a mechanism exists for count-range queries. We prove that the answer is no — for count range queries, no such mechanism exists. However, perhaps surprisingly, we prove that such a mechanism does exist for “threshold” queries, which are simply count-range queries for which either θ1 = 0 or θ2 = +∞. Furthermore, we prove that this mechanism is a two-approximation for general count-range queries.Keywords
Funding Information
- Division of Information and Intelligent Systems (IIS-0524671, CCF-0914969)
- National Institute of General Medical Sciences (R01LM011028-02)
- Division of Computing and Communication Foundations (IIS-0524671, CCF-0914969)
This publication has 14 references indexed in Scilit:
- Boosting the accuracy of differentially private histograms through consistencyProceedings of the VLDB Endowment, 2010
- Towards an axiomatization of statistical privacy and utility2010
- On the geometry of differential privacy2010
- Universally utility-maximizing privacy mechanisms2009
- A learning theory approach to non-interactive database privacy2008
- Smooth sensitivity and sampling in private data analysis2007
- Differential Privacy2006
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- Privacy-Preserving Datamining on Vertically Partitioned Databases2004
- Revealing information while preserving privacy2003