Skip to main content
Unpublished Paper
Boosting the Accuracy of Differentially Private Histograms Through Consistency
  • Michael Hay
  • Vibhor Rastogi
  • Gerome Miklau, University of Massachusetts - Amherst
  • Dan Suciu

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.

Publication Date
April 6, 2009
This is the pre-published version harvested from arXiv.
Citation Information
Michael Hay, Vibhor Rastogi, Gerome Miklau and Dan Suciu. "Boosting the Accuracy of Differentially Private Histograms Through Consistency" (2009)
Available at: