《计算机应用研究》|Application Research of Computers

基于抽样排序和层次划分的直方图发布算法

Histogram publishing algorithm based on sampling sorting and hierarchical partitioning

免费全文下载 (已被下载 次)  
获取PDF全文
作者 张润莲,叶志博,武小年
机构 1.桂林电子科技大学 广西密码学与信息安全重点实验室,广西 桂林 541004;2.广西高校云计算与复杂系统重点实验室,广西 桂林 541004
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2020)07-041-2123-03
DOI 10.19734/j.issn.1001-3695.2019.01.0010
摘要 针对直方图发布算法面临的隐私保护和数据可用性问题,提出一种基于抽样排序和层次划分的直方图发布算法。算法将指数机制和轮盘赌抽样技术相结合,对原始直方图进行抽样排序,使相似数据以较大概率排在一起;利用层次划分算法对排序后的直方图进行划分,以降低所划分分组中不同数据间的误差;最后对分组后的直方图添加拉普拉斯噪声,并恢复原始顺序,得到待发布直方图。仿真测试结果表明,该算法在满足差分隐私的前提下有效提高了发布数据的可用性。
关键词 差分隐私; 直方图发布; 轮盘赌抽样; 层次划分
基金项目 国家自然科学基金资助项目(61862011)
广西自然科学基金资助项目(2018GXNSFAA294036,2018GXNSFAA138116)
广西密码学与信息安全重点实验室项目(GCIS201705,GCIS201623)
广西高校云计算与复杂系统重点实验室项目(YF16205)
广西研究生教育创新计划资助项目(YCSW2018138,2017YJCX26)
本文URL http://www.arocmag.com/article/01-2020-07-041.html
英文标题 Histogram publishing algorithm based on sampling sorting and hierarchical partitioning
作者英文名 Zhang Runlian, Ye Zhibo, Wu Xiaonian
机构英文名 1.Guangxi Key Laboratory of Cryptography & Information Security,Guilin University of Electronic Technology,Guilin Guangxi 541004,China;2.Guangxi Colleges Key Laboratory of Cloud Computing & Complex Systems,Guilin Guangxi 541004,China
英文摘要 In order to trade-off between the privacy and accuracy of published histogram, this paper proposed a histogram publishing algorithm based on sampling sorting and hierarchical partitioning. To gather the similar data together, it introduced the exponential mechanism into the roulette sampling technology, which was used to sort the original histogram by sampling. And in order to reduce the approximation error caused by the different data lied in a data group, this paper used a hierarchical partitioning method to partition the sorted histogram. Finally, it added the Laplace noise into the grouped histogram, and restored the original histogram order to get the published histogram. The simulation results show that the algorithm can effectively improve the accuracy of published histograms on the premise of satisfying differential privacy.
英文关键词 differential privacy; histogram publishing; roulette sampling; hierarchical partitioning
参考文献 查看稿件参考文献
 
收稿日期 2019/1/20
修回日期 2019/3/5
页码 2123-2125,2147
中图分类号 TP309.2
文献标志码 A