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

By Chao Li, Michael Hay, Gerome Miklau, Yue Wang. 2014

104 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Computer Science Applications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

Citations in the corpus

Fair decision making using privacy-protected data (2019, methodology): “Therefore, we also consider the Data- and Workload-Aware (DAWA) algorithm [25].”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, unknown): “Interesting work has been done in both theCDPmodel [8, 22, 30, 33, 34, 39, 54– 56, 58, 70, 71, 75, 85, 89, 90, 100–102, 104, 105, 107] and the LDP model [13, 32, 42, 44, 91, 95–97, 108].”
Differentially Private Data Publishing and Analysis: A Survey (2017, background): “[37] proposed a matrix mechanism which can answer sets of linear counting queries.”
EKTELO: A Framework for Defining Differentially-Private Computations (2018, methodology): “These are: Vector Laplace, the partition selection operators for both DAWA [20] and AHP [37], a query selection operator used by PrivBayes [35], and a query selection operator used by the MWEM [14] algorithm that privately derives the worst-currentlyapproximated workload query.”
Differentially Private SQL with Bounded User Contribution (2019, methodology): “In this work, for clarity, we keep the description of our system conceptually simple, and explicitly do not make use of techniques like smooth sensitivity [39], tight privacy budget computation methods [22, 34], variants of the differential privacy definition [6, 8, 36], adjustment of noise levels t”