Differentially Private Spatial Decompositions
Top Cited Papers
- 1 April 2012
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Differential privacy has recently emerged as the de facto standard for private data release. This makes it possible to provide strong theoretical guarantees on the privacy and utility of released data. While it is well-understood how to release data based on counts and simple functions under this guarantee, it remains to provide general purpose techniques to release data that is useful for a variety of queries. In this paper, we focus on spatial data such as locations and more generally any multi-dimensional data that can be indexed by a tree structure. Directly applying existing differential privacy methods to this type of data simply generates noise. We propose instead the class of "private spatial decompositions'': these adapt standard spatial indexing methods such as quad trees and kd-trees to provide a private description of the data distribution. Equipping such structures with differential privacy requires several steps to ensure that they provide meaningful privacy guarantees. Various basic steps, such as choosing splitting points and describing the distribution of points within a region, must be done privately, and the guarantees of the different building blocks composed to provide an overall guarantee. Consequently, we expose the design space for private spatial decompositions, and analyze some key examples. A major contribution of our work is to provide new techniques for parameter setting and post-processing the output to improve the accuracy of query answers. Our experimental study demonstrates that it is possible to build such decompositions efficiently, and use them to answer a variety of queries privately with high accuracy.Keywords
Other Versions
This publication has 19 references indexed in Scilit:
- A firm foundation for private data analysisCommunications of the ACM, 2011
- Boosting the accuracy of differentially private histograms through consistencyProceedings of the VLDB Endowment, 2010
- Differentially private aggregation of distributed time-series with transformation and encryptionPublished by Association for Computing Machinery (ACM) ,2010
- Privacy in data publishingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Privacy integrated queriesPublished by Association for Computing Machinery (ACM) ,2009
- Universally utility-maximizing privacy mechanismsPublished by Association for Computing Machinery (ACM) ,2009
- Privacy-Preserving Data PublishingFoundations and Trends® in Databases, 2009
- Computational GeometryPublished by Springer Science and Business Media LLC ,2008
- Smooth sensitivity and sampling in private data analysisPublished by Association for Computing Machinery (ACM) ,2007
- L-diversity: privacy beyond k-anonymityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006