On Privacy-Preserving Histograms

By S. Chawla, Cynthia Dwork, Frank McSherry, Kunal Talwar. 2005

28 citations recorded by the source corpus.

We advance the approach initiated by Chawla et al. for sanitizing (census) data so as to preserve the privacy of respondents while simultaneously extracting "useful" statistical information. First, we extend the scope of their techniques to a broad and rich class of distributions, specifically, mixtures of high-dimensional balls, spheres, Gaussians, and other "nice" distributions. Second, we randomize the histogram constructions to preserve spatial characteristics of the data, allowing us to approximate various quantities of interest, e. g., cost of the minimum spanning tree on the data, in a privacy-preserving fashion.

Subfields: Artificial Intelligence, Computer Science Applications, Signal Processing

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

1. Lalitha Sankar
2. H. Vincent Poor
3. S. Rajagopalan
4. Isabel Wagner
5. David Eckhoff
6. Flávio du Pin Calmon

In Computer Science Applications

1. Lalitha Sankar
2. H. Vincent Poor
3. S. Rajagopalan
4. Isabel Wagner
5. David Eckhoff

In Signal Processing

1. Lalitha Sankar
2. H. Vincent Poor
3. S. Rajagopalan

Citations in the corpus

• An information-theoretic approach to privacy (2010, methodology): “Similarly, utility in privacypreserving techniques such as clustering [4] and histograms [16] is assumed to be guaranteed as a direct result of the methods used; for example, in [ 16 ] it is shown that approximation algorithms that can run on original histograms can also run on the sanitized histogr”
• Utility-Privacy Tradeoffs in Databases: An Information-Theoretic Approach (2011, background): “The problem of privacy and information leakage has been studied for several decades by multiple research communities; information-theoretic approaches to the problem are few and far in between and have primarily focused on using information-theoretic metrics.”
• Privacy-preserving data publishing: A survey of recent developments (2010, unknown): “2007] PM min. error optimal Greedy Personalized [Xiao and Tao 2006b] SG,CG ILoss minimal t-Closeness Incognito [Li et al. 2007] FG,RS DM optimal Table Linkage SPALM [Nergiz et al. 2007] FG DM optimal MPALM [Nergiz et al. 2007] MG heuristics minimal Probabilistic Attack Cross-Training Round Sanitiz”