|
|
|
| A Differentially Private Histogram Publication Algorithm for Arbitrary Range Tree Structure |
| WU Ying-Jie, CHEN Hong, WANG Yi-Lei, SUN Lan |
| College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116 |
|
|
|
|
Abstract In the existing methods for differentially private histogram publication, a histogram is mapped to a perfect m-ary range tree. The accuracies of queries are boosted through consistency constraints of the queries. However, not all histograms in real application can be mapped to perfect m-ary range trees directly. In this paper, a range tree structure, k-range tree, is firstly put forward. By k-range tree, an arbitrary histogram is mapped to a range tree. Secondly, the theoretical analysis shows that for differentially private histogram publication for arbitrary range tree structure, the error of range counting queries still can be further reduced by solving the best linear unbiased estimation of the tree node values through consistency. Finally, a differentially private histogram publication algorithm based on local best linear unbiased estimation(LBLUE) for arbitrary range tree structure is proposed. Experiment is carried out to compare LBLUE and the traditional algorithms on the accuracy of range counting queries in the released histogram and the algorithm efficiency. Experimental results show that LBLUE is effective and feasible.
|
|
Received: 09 December 2014
|
|
|
|
|
|
[1] Zhou S G, Li F, Tao Y F, et al. Privacy Preservation in Database Applications: A Survey. Chinese Journal of Computers, 2009, 32(5): 847-861 (in Chinese)
(周水庚,李 丰,陶宇飞,等.面向数据库应用的隐私保护研究综述.计算机学报, 2009, 32(5): 847-861)
[2] Fung B C M, Wang K, Chen R, et al. Privacy-Preserving Data Publishing: A Survey on Recent Developments[EB/OL]. [2014-11-30]. http://www.cs.sfu.ca/~wangk/pub/FWCY10csur.pdf
[3] Sweeney L. k-Anonymity: A Model for Protecting Privacy. International Journal on Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570
[4] Machanavajjhala A, Gehrke J, Kifer D, et al. l-Diversity: Privacy beyond k-Anonymity // Proc of the 22nd International Conference on Data Engineering. Atlanta, USA, 2006: 24-35
[5] Li N H, Li T C, Venkatasubramanian S. t-Closeness: Privacy beyond k-Anonymity and l-Diversity // Proc of the 23rd International Conference on Data Engineering. Istanbul, Turkey, 2007: 106-115
[6] Dwork C. Differential Privacy[EB/OL]. [2014-11-30]. http://research.microsoft.com/en-us/projects/databaseprivacy/dwork.pdf
[7] Dwork C, McSherry F, Nissim K, et al. Calibrating Noise to Sensitivity in Private Data Analysis // Proc of the 3rd Conference on Theory of Cryptography. New York, USA, 2006: 265-284
[8] Zhang X J, Meng X F. Differential Privacy in Data Publication and Analysis. Chinese Journal of Computers, 2014, 37(4): 927-949 (in Chinese)
(张啸剑,孟小峰.面向数据发布和分析的差分隐私保护.计算机学报, 2014, 37(4): 927-949)
[9] Xiao X K, Wang G Z, Gehrke J. Differential Privacy via Wavelet Transforms. IEEE Trans on Knowledge and Data Engineering, 2011, 23(8): 1200-1214
[10] Cormode G, Procopiuc C M, Srivastava D, et al. Differentially Private Summaries for Sparse Data // Proc of the 15th International Conference on Database Theory. Berlin, Germany, 2012: 299-311
[11] Xu J, Zhang Z J, Xiao X K, et al. Differentially Private Histogram Publication. The VLDB Journal, 2013, 22(6): 797-822
[12] Acs G, Castelluccia C, Chen R. Differentially Private Histogram Publishing through Lossy Compression // Proc of the 12th IEEE International Conference on Data Mining. Brussels, Belgium, 2012. DOI: 10.1109/ICDM.2012.80
[13] Hay M, Rastogi V, Miklau G, et al. Boosting the Accuracy of Di-fferentially Private Histograms through Consistency. Proceedings of the VLDB Endowment, 2010, 3(1/2): 1021-1032
[14] Peng S F, Yang Y, Zhang Z J, et al. DP-Tree: Indexing Multi-dimensional Data under Differential Privacy(Abstract Only) // Proc of the ACM SIGMOD International Conference on Management of Data. Scottsdale, USA, 2012: 864
[15] Pass G, Chowdhury A, Torgeson C. A Picture of Search // Proc of the 1st International Conference on Scalable Information Systems. Hong Kong, China, 2006. DOI: 10.1145/1146847 |
|
|
|
2015, Vol. 28 
