Differentially Private Spatial Decompositions

Details Differentially Private Spatial Decompositions Differentially Private Spatial Decompositions

2011-03-26

arxiv.org/abs/1103.5170v3

Computer Science

Databases

ICDE 2012 (supplementary acknowledgments)

Scientific paper

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-known how to release data based on counts and simple functions under this guarantee, it remains to provide general purpose techniques to release different kinds of data. In this paper, we focus on spatial data such as locations and more generally any data that can be indexed by a tree structure. Directly applying existing differential privacy methods to this type of data simply generates noise. Instead, we introduce a new class of "private spatial decompositions": these adapt standard spatial indexing methods such as quadtrees 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 primitives, 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. 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.

Affiliated with

Also associated with

No associations

Rating

Differentially Private Spatial Decompositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Differentially Private Spatial Decompositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Differentially Private Spatial Decompositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-94572