A data- and workload-aware algorithm for range queries under differential privacy

TLDR

The authors propose a data‑ and workload‑aware algorithm for answering range queries under ε‑differential privacy that achieves lower error than existing methods. The algorithm privately learns a data‑dependent bucket partition, then privately estimates bucket counts with noise calibrated to the query workload, ensuring differential privacy. Experiments on diverse real datasets demonstrate that the data‑dependent approach yields significant error reductions on both easy and hard databases.

Abstract

We describe a new algorithm for answering a given set of range queries under ε-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.