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

Histogram publishing algorithm based on sampling sorting and hierarchical partitioning

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

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.