Boosting the Accuracy of Differentially Private Histograms
Through Consistency
PVLDB, 3 (1):
1021-1032 (2010)Zusammenfassung
We show that it is possible to sign cantly improve the accuracy of a general class of histogram queries while satisfying di erential 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 nal output is di erentially-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