基于二叉树结构的差分隐私直方图发布算法

Differential Private Histogram Publication Algorithm Based on Binary Tree

针对StructureFirst模型在直方图重构中不能自适应选择重构的桶个数、划分较复杂且不能发布动态数据的问题，首先采用二叉树结构将直方图加以重构，而后通过向其统计值添加噪声来满足差分隐私，最后通过滑动窗口实现动态发布。实验证明，所提算法在保护用户隐私信息的同时具有更高的划分准确度和划分效率。

The StructureFirst model in histogram reconstruction has existed the problems such as lack of the ability to choose the bucket number and to release dynamic data and the situation of higher complexity. Firstly, the histogram is reconsturcted based on the binary tree. Then, noise is added to the data after the reconstruction to meet the differential privacy. Finally,the histogram is released for each timestamp by sliding window. Experimental results show that the proposed algorithm has higher classification accuracy and partition efficiency while the user＇s privacy information can be protected.