An Adaptive Mechanism for Accurate Query Answering under Differential Privacy
Differential privacy guarantees that information released about participants in a data set will be virtually indistinguishable whether or not their personal data is included. There are now many algorithms satisfying differential privacy, however, when adopting differential privacy, users must reason carefully about alternative mechanisms and the formulation of their task. The authors propose a novel mechanism for answering sets of counting queries under differential privacy. Given a workload of counting queries, the mechanism automatically selects a different set of "Strategy" queries to answer privately, using those answers to derive answers to the workload. The main algorithm proposed in this paper approximates the optimal strategy for any workload of linear counting queries.