Ascending partition method for differentially private histogram publication

作者：Xu, Yangyang; Liu, Zhaobin^*; Hu, Zhonglian

来源：Computer Systems Science and Engineering, 2016, 31(2): 173-179.

Differential privacy has emerged as a promising scheme for protecting individual privacy in data release and data mining against adversaries with arbitrary background knowledge. It is often used to provide strong privacy guarantee in various types of data release, in particular, a histogram, which gives statistical summaries of the data set. Existing works on releasing sensitive data differentially with histogram mostly focus on boosting the accuracy and utility while preserving the individual privacy. This paper investigates how to increase the accuracy further.
The authors propose a novel APT (Ascending Partitioning and Tuning) method. First of all, it sorts each bin in original histogram according to its count. Then, all bins will be grouped into several union regions and independent Laplace noise will be injected into each region. Compared with existing works, our method optimizes the uniformity of region on the basis of data set. Finally, the count of each region will be assigned to each bin in it averagely, then the noisy histogram could be released and used for range queries. APT uses low Laplace noise injection to achieve epsilon-differential privacy. Meanwhile, as shown both theoretically and experimentally, our mechanism ensures the sanitized histogram a better accuracy for arbitrary range queries than other ones in similar works.

• 出版日期2016-3
• 单位大连海事大学