DPCube: Differentially private histogram release through multidimensional partitioning

作者：Xiao Yonghui^*; Xiong Li; Fan Liyue; Goryczka Slawomir; Li Haoran

来源：Transactions on Data Privacy, 2014, 7(3): 195-222.

• Data release
• Differential privacies
• Histogram
• Individual privacy
• Input datas
• Partitioning strategies
• Privacy preserving
• Record linkage

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.

• 出版日期2014
• 单位EMORY University; emory university; Emory university; EMORY UNIVERSITY