On Optimal Differentially Private Mechanisms for Count-Range Queries.
On Optimal Differentially Private Mechanisms for Count-Range Queries.
复制标题
关于计数范围查询的最优差分私有机制。
DOI：
10.1145/2448496.2448528
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Naughton,JeffreyF
中科院分区：
文献类型：
--
作者：
Zeng,Chen;Cai,Jin-Yi;Lu,Pinyan;Naughton,JeffreyF
虽然有一个大的和不断增长的机构的文献差异私人机制回答各类查询，据我们所知，“计数范围”查询还没有被研究。这是一类自然的查询，它们询问“关系中的行数是否满足两个整数θ 1和θ2之间的给定谓词？这样的查询可以被看作是一种简单的SQL“拥有”查询。我们开始通过开发一个可证明的最优差分私有mechanisim计数范围查询的单个消费者。对于计数查询（与计数查询相反），Ghosh等人。[9]提供了一种差异私有机制，可以同时最大化多个消费者的效用。这就提出了一个问题，即是否存在这样一种用于计数范围查询的机制。我们证明，答案是否定的-计数范围查询，没有这样的机制存在。然而，也许令人惊讶的是，我们证明了这样的机制确实存在的“阈值”查询，这是简单的计数范围查询，其中θ1= 0或θ2= +∞。此外，我们证明了这种机制是一般的计数范围查询的两个近似。
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 θ1and θ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 countrange 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.