Differentially private histogram publication

作     者：Xu, Jia Zhang, Zhenjie Xiao, Xiaokui Yang, Yin Yu, Ge Winslett, Marianne 

作者机构：Northeastern Univ Coll Informat Sci & Engn Shenyang Peoples R China Singapore Pte Ltd Adv Digital Sci Ctr Singapore Singapore Nanyang Technol Univ Sch Comp Engn Singapore 639798 Singapore Univ Illinois Dept Comp Sci Urbana IL USA 

出 版 物：《VLDB JOURNAL》 (国际大型数据库杂志)

年 卷 期：2013年第22卷第6期

页      面：797-822页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Basic Research Program of China (973) [2012CB316201] National Natural Science Foundation of China [61033007, 61003058] Fundamental Research Funds for the Central Universities [N100704001] SERC from Singapore's A*STAR [102 158 0074] Nanyang Technological University under SUG [M58020016] Nanyang Technological University under AcRF [RG 35/09] Agency for Science, Technology and Research (Singapore) under SERG 

主　　题：Differential privacy Database query processing Histogram 

摘      要：Differential privacy (DP) is a promising scheme for releasing the results of statistical queries on sensitive data, with strong privacy guarantees against adversaries with arbitrary background knowledge. Existing studies on differential privacy mostly focus on simple aggregations such as counts. This paper investigates the publication of DP-compliant histograms, which is an important analytical tool for showing the distribution of a random variable, e.g., hospital bill size for certain patients. Compared to simple aggregations whose results are purely numerical, a histogram query is inherently more complex, since it must also determine its structure, i.e., the ranges of the bins. As we demonstrate in the paper, a DP-compliant histogram with finer bins may actually lead to significantly lower accuracy than a coarser one, since the former requires stronger perturbations in order to satisfy DP. Moreover, the histogram structure itself may reveal sensitive information, which further complicates the problem. Motivated by this, we propose two novel mechanisms, namely NoiseFirst and StructureFirst, for computing DP-compliant histograms. Their main difference lies in the relative order of the noise injection and the histogram structure computation steps. NoiseFirst has the additional benefit that it can improve the accuracy of an already published DP-compliant histogram computed using a naive method. For each of proposed mechanisms, we design algorithms for computing the optimal histogram structure with two different objectives: minimizing the mean square error and the mean absolute error, respectively. Going one step further, we extend both mechanisms to answer arbitrary range queries. Extensive experiments, using several real datasets, confirm that our two proposals output highly accurate query answers and consistently outperform existing competitors.