一种基于桶重构的差分隐私直方图发布方法
|
摘要
差分隐私(Differential Privacy,DP)是一种新型的隐私保护模型,而直方图是差分隐私保护下数据发布的一种重要形式。现有的差分隐私直方图发布技术未能高效处理存在离群点的数据集。针对这一问题,基于桶重构思想,提出一种高效的、面向存在离群点数据集的差分隐私直方图发布的R-G-I方法。该方法包括三个重要的算法,第一步用梯度回归算法处理原始数据集,第二步用基于桶重构的贪心算法处理经第一步处理后形成的数据集,第三步用保序回归算法处理经第二步处理后形成的数据集。采用不同特点的真实数据集进行实验,结果验证了提出的直方图发布方法针对含有离群点的数据集的准确性和有效性。
DP(Differential Privacy) is a new type of privacy protection model, while histogram an important form of data distribution under differential privacy protection. The existing differential privacy histogram publishing techniques fail to deal with data sets with outliers efficiently. Aiming at this problem, based on the idea of bucket reconstruction, an efficient R-G-I method for differential privacy histogram publishing with outlier data sets is proposed. The method involves three important algorithms: The first step is to process the original data set with a gradient regression algorithm; the second step is to use the greedy algorithm based on bucket reconstruction to process the data set formed after the first step; the third step is to use the orderpreserving regression algorithm to process the data set formed after the second step. Experiments on real data sets with different characteristics indicate the accuracy and validity of the proposed histogram publishing method for data sets with outliers.
DP(Differential Privacy) is a new type of privacy protection model, while histogram an important form of data distribution under differential privacy protection. The existing differential privacy histogram publishing techniques fail to deal with data sets with outliers efficiently. Aiming at this problem, based on the idea of bucket reconstruction, an efficient R-G-I method for differential privacy histogram publishing with outlier data sets is proposed. The method involves three important algorithms: The first step is to process the original data set with a gradient regression algorithm; the second step is to use the greedy algorithm based on bucket reconstruction to process the data set formed after the first step; the third step is to use the orderpreserving regression algorithm to process the data set formed after the second step. Experiments on real data sets with different characteristics indicate the accuracy and validity of the proposed histogram publishing method for data sets with outliers.
引文
[1]周水庚,李丰,陶宇飞等.面向数据库应用的隐私保护研究综述[J].计算机学报,2009,32(05):847-861.ZHOU Shui-geng,LI Feng,TAO Yu-fei,et al.Review of Privacy Protection for Database Applications[J].Journal of Computer Science,2009,32(05):847-861.
[2]Sweeney L.k-anonymity:A Model for Protecting Privacy[J].International Journal onUncertainty,Fuzziness and Knowledge Based Systems,2002,10(05):557-570.
[3]Machanavajjhala A,Gehrke J,Kifer D,et a1.1-diversity:Privacy Beyond k-anonymity[J].ACMTransactions on Knowledge Discovery from Data(TKDD),2007,1(01):3.
[4]Li N,Li T.t-closeness:Privacy Beyond k-anonymity and1-diversity[C].Proceedings of the 23th International Conference on Data Engineering(ICDE).,2007:106-115.
[5]Dwork C.Differential Privacy[C].Proceedings of the 33th Intemational Colloquium onAutomata,Languages and Programming(ICALP).2006:1-12.
[6]Dwork C,McSherry F,Nissim K,et a1.Calibrating Noise to Sensitivity in Private Dataanalysis[C].Proceedings of the 43 Theory of Cryptography Conference(TCC).2006:363-385.
[7]Smith A.Privacy-preserving Statistical Estimation with Optimal Convergence Rate[C].Proceedings on the 43th Annual ACM Symposium Oil Theory of Computing(STOC).201l:813-822.
[8]Hay M,Rastogi V,Miklau G,et a1.Boosting the Accuracy of Differentially Privatehistograms through Consistency[C].Proceedings of the 36th Conference of Very Large Databases(VLDB).2010:1021-1032.
[9]Xu J,Zhang Z,Xiao X,et a1.Differentially Private Histogram Publication[C].Proceedings of IEEE 28th International Conference on Data Engineering(ICDE).2012:32-43.
[10]Acs G,Chen R.Differentially Private Histogram Publishing through Lossy Compression[C].IEEE International Conference on Data Mining(ICDM).2012:84-95.
[11]邵波,韩启龙.差分隐私直方图发布方法的研究[D].哈尔滨:哈尔滨工程大学,2016.SHAO Bo,HAN Qi-long.Research on Differential Privacy Histogram Publishing Method[D].Harbin:Harbin Engineering University,2016.
[12]Campos N B D,Campos N B D.Noise Analysis and Intervention in Speech School Environment:Regular Private and Public Schools[J].Rev Cefac,2014,16(01):83-91.
[13]Riboni D,Bettini C.Differentially-private Release of Check-in Data for Venuere Commendation[C].Pervasive Computing and Communications,2014:190-198.
[2]Sweeney L.k-anonymity:A Model for Protecting Privacy[J].International Journal onUncertainty,Fuzziness and Knowledge Based Systems,2002,10(05):557-570.
[3]Machanavajjhala A,Gehrke J,Kifer D,et a1.1-diversity:Privacy Beyond k-anonymity[J].ACMTransactions on Knowledge Discovery from Data(TKDD),2007,1(01):3.
[4]Li N,Li T.t-closeness:Privacy Beyond k-anonymity and1-diversity[C].Proceedings of the 23th International Conference on Data Engineering(ICDE).,2007:106-115.
[5]Dwork C.Differential Privacy[C].Proceedings of the 33th Intemational Colloquium onAutomata,Languages and Programming(ICALP).2006:1-12.
[6]Dwork C,McSherry F,Nissim K,et a1.Calibrating Noise to Sensitivity in Private Dataanalysis[C].Proceedings of the 43 Theory of Cryptography Conference(TCC).2006:363-385.
[7]Smith A.Privacy-preserving Statistical Estimation with Optimal Convergence Rate[C].Proceedings on the 43th Annual ACM Symposium Oil Theory of Computing(STOC).201l:813-822.
[8]Hay M,Rastogi V,Miklau G,et a1.Boosting the Accuracy of Differentially Privatehistograms through Consistency[C].Proceedings of the 36th Conference of Very Large Databases(VLDB).2010:1021-1032.
[9]Xu J,Zhang Z,Xiao X,et a1.Differentially Private Histogram Publication[C].Proceedings of IEEE 28th International Conference on Data Engineering(ICDE).2012:32-43.
[10]Acs G,Chen R.Differentially Private Histogram Publishing through Lossy Compression[C].IEEE International Conference on Data Mining(ICDM).2012:84-95.
[11]邵波,韩启龙.差分隐私直方图发布方法的研究[D].哈尔滨:哈尔滨工程大学,2016.SHAO Bo,HAN Qi-long.Research on Differential Privacy Histogram Publishing Method[D].Harbin:Harbin Engineering University,2016.
[12]Campos N B D,Campos N B D.Noise Analysis and Intervention in Speech School Environment:Regular Private and Public Schools[J].Rev Cefac,2014,16(01):83-91.
[13]Riboni D,Bettini C.Differentially-private Release of Check-in Data for Venuere Commendation[C].Pervasive Computing and Communications,2014:190-198.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |