Full Citation

Title: Understanding Hierarchical Methods for Differentially Private Histograms

Citation Type: Miscellaneous

Publication Year: 2013

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: In recent years, many approaches to differentially privately publish histograms have been proposed. Several approaches rely on constructing tree structures in order to decrease the error when answer large range queries. In this paper, we examine the factors affecting the accuracy of hierarchical a pproaches by studying the mean squared error (MSE) when answering range queries. We start with one-dimensional histograms, and analyze how the MSE changes with different branching factors, after employing constrained inference, and with different methods to allocate the privacy budget among hierarchy levels. Our analysis and experimental results show that combining the choice of a good branching factor with constrained inference outperform the current state of the art. Finally, we extend our analysis to multidimensional histograms. We show that the benefits from employing hierarchical methods beyond a single dimension are significantly diminished, and when there are 3 or more dimensions, it is almost always better to use the Flat method instead of a hierarchy.

User Submitted?: No

Authors: Qardaji, Wahbeh; Li, Ninghui; Yang, Weining

Publisher: Purdue University

Data Collections: IPUMS USA

Topics: Methodology and Data Collection

Countries: