DPCube: Differentially Private Histogram Release through Multidimensional Partitioning

Details DPCube: Differentially Private Histogram Release through Multidimensional Partitioning DPCube: Differentially Private Histogram Release through Multidimensional Partitioning

2012-02-24

arxiv.org/abs/1202.5358v1

Computer Science

Databases

14 pages

Scientific paper

Differential privacy is a strong notion for protecting individual privacy in privacy preserving data analysis or publishing. In this paper, we study the problem of differentially private histogram release for random workloads. We study two multidimensional partitioning strategies including: 1) a baseline cell-based partitioning strategy for releasing an equi-width cell histogram, and 2) an innovative 2-phase kd-tree based partitioning strategy for releasing a v-optimal histogram. We formally analyze the utility of the released histograms and quantify the errors for answering linear queries such as counting queries. We formally characterize the property of the input data that will guarantee the optimality of the algorithm. Finally, we implement and experimentally evaluate several applications using the released histograms, including counting queries, classification, and blocking for record linkage and show the benefit of our approach.

Affiliated with

Also associated with

No associations

Rating

DPCube: Differentially Private Histogram Release through Multidimensional Partitioning 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 DPCube: Differentially Private Histogram Release through Multidimensional Partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and DPCube: Differentially Private Histogram Release through Multidimensional Partitioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-78130