Boosting the accuracy of differentially private histograms through consistency

TLDR

The study aims to enhance the accuracy of differentially private histogram queries by selecting specific queries and leveraging consistency constraints on the noisy output. The method selects a set of queries, applies consistency constraints, and post‑processes the noisy results to compute the most likely consistent input. The approach yields differentially private, consistent outputs that are often substantially more accurate, enabling precise estimation of graph degree sequences and accurate arbitrary‑range histogram queries.

Abstract

We show that it is possible to significantly improve the accuracy of a general class of histogram queries while satisfying differential privacy. Our approach carefully chooses a set of queries to evaluate, and then exploits consistency constraints that should hold over the noisy output. In a post-processing phase, we compute the consistent input most likely to have produced the noisy output. The final output is differentially-private and consistent, but in addition, it is often much more accurate. We show, both theoretically and experimentally, that these techniques can be used for estimating the degree sequence of a graph very precisely, and for computing a histogram that can support arbitrary range queries accurately.