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

来源：计算机应用研究杂志2020年第7期北京时间：

作者：张润莲,叶志博,武小年,

单位：1.桂林电子科技大学广西密码学与信息安全重点实验室,广西桂林541004；2.广西高校云计算与复杂系统重点实验室,广西桂林541004；

摘要：针对直方图发布算法面临的隐私保护和数据可用性问题，提出一种基于抽样排序和层次划分的直方图发布算法。算法将指数机制和轮盘赌抽样技术相结合，对原始直方图进行抽样排序，使相似数据以较大概率排在一起；利用层次划分算法对排序后的直方图进行划分，以降低所划分分组中不同数据间的误差；最后对分组后的直方图添加拉普拉斯噪声，并恢复原始顺序，得到待发布直方图。仿真测试结果表明，该算法在满足差分隐私的前提下有效提高了发布数据的可用性。

关键词：差分隐私,直方图发布,轮盘赌抽样,层次划分,

基金资助：国家自然科学基金资助项目(61862011)；广西自然科学基金资助项目(2018GXNSFAA294036,2018GXNSFAA138116)；广西密码学与信息安全重点实验室项目(GCIS201705,GCIS201623)；广西高校云计算与复杂系统重点实验室项目(YF16205)；广西研究生教育创新计划资助项目(YCSW2018138,2017YJCX26)；；