4.4 Article

A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy

Journal

PROCEEDINGS OF THE VLDB ENDOWMENT
Volume 7, Issue 5, Pages 341-352

Publisher

ASSOC COMPUTING MACHINERY
DOI: 10.14778/2732269.2732271

Keywords

-

Funding

  1. NSF [CNS-1012748, IIS-0964094, CNS-1129454]
  2. CRA/CCC through CI Fellows grant [1019343]

Ask authors/readers for more resources

We describe a new algorithm for answering a given set of range queries under epsilon-differential privacy which often achieves substantially lower error than competing methods. Our algorithm satisfies differential privacy by adding noise that is adapted to the input data and to the given query set. We first privately learn a partitioning of the domain into buckets that suit the input data well. Then we privately estimate counts for each bucket, doing so in a manner well-suited for the given query set. Since the performance of the algorithm depends on the input database, we evaluate it on a wide range of real datasets, showing that we can achieve the benefits of data-dependence on both easy and hard databases.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.4
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available