|本期目录/Table of Contents|

[1]孙 岚,吴英杰,张玺霖,等.基于桶划分的差分隐私直方图发布贪心算法[J].厦门大学学报(自然科学版),2013,52(06):770.[doi:10.6043/j.issn.0438-0479.2013.06.007]
 SUN Lan*,WU Ying-jie,ZHANG Xi-lin,et al.Greedy Algorithm Based on Bucket Partitioning for Differentially Private Histogram Publication[J].Journal of Xiamen University(Natural Science),2013,52(06):770.[doi:10.6043/j.issn.0438-0479.2013.06.007]
点击复制

基于桶划分的差分隐私直方图发布贪心算法(PDF)
分享到:

《厦门大学学报(自然科学版)》[ISSN:0438-0479/CN:35-1070/N]

卷:
52卷
期数:
2013年06期
页码:
770
栏目:
出版日期:
2013-11-20

文章信息/Info

Title:
Greedy Algorithm Based on Bucket Partitioning for Differentially Private Histogram Publication
作者:
孙 岚吴英杰张玺霖谢 怡
1.福州大学数学与计算机科学学院,福建 福州 350108; 2.厦门大学信息科学与技术学院,福建 厦门 361005
Author(s):
SUN Lan1*WU Ying-jie1ZHANG Xi-lin1XIE Yi2
1.College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China; 2.School of Information Science and Engineering,Xiamen University,Xiamen 361005,China
关键词:
差分隐私 直方图发布 桶划分 贪心算法 红黑树
Keywords:
differential privacy histogram publication bucket partitioning greedy algorithm red-black tree
分类号:
TP 311
DOI:
10.6043/j.issn.0438-0479.2013.06.007
文献标志码:
-
摘要:
现有的差分隐私直方图发布技术未能高效处理存在大量低频计数值数据集发布中的隐私保护问题.基于桶划分的思想,提出一种高效的、面向存在大量低频计数值数据集的差分隐私直方图发布贪心算法.算法采用基于邻近桶合并的贪心策略,并利用红黑树对合并过程进行优化.实验对本文算法发布数据的可用性及算法效率与同类算法进行比较分析.实验结果表明,该算法是有效可行的.
Abstract:
Existed methods of differential privacy histogram publication cannot efficiently protect the privacy of data sets which have a large amount of small counts for different values of certain attribute.We proposed an efficient greedy algorithm to handle the differential privacy histogram publish problem of this particular data sets.The greedy algorithm adopted the merging strategies of closest neighbor barrel,and optimized the merging procedure using the red-black tree.Many simulation experiments were launched to compare the proposed algorithm with similar algorithms in terms of the availability of published data and the efficiency of algorithm.The simulation results verify that the greedy algorithm is efficient.

参考文献/References:


[1] Sweeney L.k-anonymity:a model for protecting privacy[J].International Journal on Uncertainty,Fuzziness and Knowledge Based Systems,2002,10(5):557-570.
[2] Machanavajjhala A,Gehrke J,Kifer D,et al.l-diversity:privacy beyond k-anonymity[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2007,1(1):3.
[3] Li N,Li T.t-closeness:privacy beyond k-anonymity and l-diversity[C]∥Proc of the 23rd International Conference on Data Engineering(ICDE).Istanbul,Turkey:IEEE,2007:106-115.
[4] Dwork C.Differential privacy[C]∥Proc of the 33rd International Colloquium on Automata,Languages and Programming(ICALP).Venice,Italy:Springer Berlin Heidelberg,2006:1-12.
[5] Dwork C,McSherry F,Nissim F K,et al.Calibrating noise to sensitivity in private data analysis[C]∥Proc of the 3rd Theory of Cryptography Conference(TCC).New York,USA:Springer Berlin Heidelberg,2006:363-385.
[6] Dwork C.Differential privacy:a survey of results[C]∥Proc of the 5th Theory and Applications of Models of Computation(TAMC).Xi’an,China:Springer Berlin Heidelberg,2008:1-19.
[7] Dwork C,Smith A.Differential privacy for statistics:what we know and what we want to learn[J].Journal of Privacy and Confidentiality,2009,1(2):135-154.
[8] Hay M,Rastogi V,Miklau G,et al.Boosting the accuracy of differentially private histograms through consistency[C]∥Proc of the 36th Conference of Very Large Databases(VLDB).Istanbul,Turkey:VLDB Endowment,2010:1021-1032.
[9] Xiao X,Wang G,Gehrke J.Differential privacy via wavelet transforms[J].IEEE Transactions on Knowledge and Data Engineering(TKDE),2011,23(8):1200-1214.
[10] Li C,Hay M,Rastogi V,et al.Optimizing linear counting queries under differential privacy[C]∥Proc of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems(PODS).Indianapolis,USA:ACM,2010:123-134.
[11] Li C,Miklau G.An adaptive mechanism for accurate query answering under differential privacy[C]∥Proc of the 38th Conference of Very Large Databases(VLDB).Istanbul,Turkey:VLDB Endowment,2012:514-525.
[12] Xiao X,Bender G,Hay M,et al.iReduct:differential privacy with reduced relative errors[C]∥Proc of the 2011 ACM SIGMOD International Conference on Management of Data(SIGMOD).Athens:ACM,2011:229-240.
[13] Peng S,Yang Y,Zhang Z,et al.DP-tree:indexing multi-dimensional data under differential privacy[C]∥Proc of the 2012 ACM SIGMOD International Conference on Management of Data(SIGMOD).Scottsdale:ACM,2012:864.
[14] Xu J,Zhang Z,Xiao X,et al.Differentially private histogram publication[C]∥Proc of IEEE 28th International Conference on Data Engineering(ICDE).Washington,DC:IEEE,2012:32-43.

备注/Memo

备注/Memo:

*通信作者:lsun@fzu.edu.cn
更新日期/Last Update: 2013-11-20