基于桶划分的差分隐私直方图发布贪心算法  

Greedy Algorithm Based on Bucket Partitioning for Differentially Private Histogram Publication

作　　者：孙岚[1] 吴英杰[1] 张玺霖[1] 谢怡[2] 

机构地区：[1]福州大学数学与计算机科学学院,福建福州350108 [2]厦门大学信息科学与技术学院,福建厦门361005

出　　处：《厦门大学学报（自然科学版）》2013年第6期770-775,共6页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金项目(61300026);中央高校基本科研业务费专项资金(2010121066);深圳市战略性新兴产业发展专项资金;福州大学科技发展基金项目(2012.XQ-27)

摘　　要：现有的差分隐私直方图发布技术未能高效处理存在大量低频计数值数据集发布中的隐私保护问题.基于桶划分的思想,提出一种高效的、面向存在大量低频计数值数据集的差分隐私直方图发布贪心算法.算法采用基于邻近桶合并的贪心策略,并利用红黑树对合并过程进行优化.实验对本文算法发布数据的可用性及算法效率与同类算法进行比较分析.实验结果表明,该算法是有效可行的.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.

关 键 词：差分隐私 直方图发布 桶划分 贪心算法 红黑树 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]