Boosting the accuracy of differentially private histograms through consistency

By Michael Hay, Vibhor Rastogi, Gerome Miklau, Dan Suciu. 2009

314 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

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

Citations in the corpus

Functional Mechanism: Regression Analysis under Differential Privacy (2012, background): “In particular, Hay et al. [13], Li et al. [17], Xiao et al. [30], and Cormode et al. [6] present methods for minimizing the worst-case error of a given set of count queries; Barak et al. [2] and Ding et al. [8] consider the publication of data cubes; Xu et al. [31] and Li et al. [18] focus on…”
The geometry of differential privacy: the sparse and approximate cases (2012, neutral): “Therefore, deﬁning err and opt in terms of integer histograms (i.e. taking err does not change the asymptotics of our theorems.”
Privacy via the Johnson-Lindenstrauss Transform (2012, neutral): “[22] on constrained inference and application of decision theory by Lin and Kifer [30].”
PrivBayes: private data release via bayesian networks (2014, background): “Informally, this model requires that what can be learned from the released data is (approximately) the same, whether or not any particular individual was included in the input database.”
A Guide to Differential Privacy Theory in Social Network Analysis (2012, unknown): “This very low sensitivity makes histograms a useful tool in differentially private data-mining [4], [5], [6].”
The Optimal Noise-Adding Mechanism in Differential Privacy (2012, background): “[51] show that one can improve the accuracy for a general class of histogram queries, by exploiting the consistency constraints on the query output, and Li et al.”
Differentially private histogram publication (2012, methodology): “On the other hand, the remaining methods (i.e., Boost, Privlet, and StructureFirst) all adopt a hierarchy tree structure to reorganize the original data in order to improve the query accuracy of range queries with large ranges.”
Differentially Private High-Dimensional Data Publication via Sampling-Based Inference (2015, background): “[12] exploit the consistency constraints that should hold over the noisy output to improve accuracy.”
Is Interaction Necessary for Distributed Private Learning? (2017, methodology): “Our one-dimensional algorithm is based on a novel reduction of the general one-dimensional convex optimization to the median problem (a special case), followed by a noninteractive local algorithm for the median that uses a tree-based technique for simultaneously approximating 1D range queries (that ”
DP-WHERE: Differentially private modeling of human mobility (2013, methodology): “Next, the noisy matrix M̂ is converted to a CDF by applying post-processing techniques [13] to further reduce the noise.”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, methodology): “, ĉ ′ 100] via isotonic regression [57] minV̂ ′ ∥V̂ ′ − V̂ ∥2 s .”
Differentially private summaries for sparse data (2012, methodology): “The work of [15, 11] describes how to perform post-processing on dyadic range counts”
Differentially private anonymized histograms (2019, methodology): “Previous results: The problem of releasing anonymized histograms was first studied by [12, 4] in the context of degree distributions of graphs.”
Towards an axiomatization of statistical privacy and utility (2010, background): “Our first axiom, Axiom 2.1.1 deals with the effects of postprocessing the sanitized data (this axiom has been observed to hold in differential privacy [14] [24] [2] [42], but we do not tie it to any specific privacy definition).”
An Adaptive Mechanism for Accurate Query Answering under Differential Privacy (2012, unknown): “Xiao et al. [21] first answer a set of wavelet basis queries, while Hay et al. [13] use a hierarchical set of counting queries which recursively decompose the domain.”
Differentially private data release for data mining (2011, methodology): “Current techniques that adopt the non-interactive approach publish contingency tables or marginals of the raw data [9, 1, 44, 16] (see Section 2 for more discussion).”
Optimizing linear counting queries under differential privacy (2009, methodology): “We begin by analyzing two techniques proposed recently [17, 11].”
Differentially Private K-Means Clustering (2015, background): “Most non-interactive approaches aim at developing solutions to answer histogram or range queries accurately [10, 33, 14, 6].”
Differentially Private Projected Histograms: Construction and Use for Prediction (2012, background): “[12] explore tailoring of histograms for answering multiple queries for which we have consistency constraints, for example given as subset sums of query results.”