基于线段树结构的差分隐私数据发布算法

Differential Privacy Data Publishing Algorithm Based on Segment Tree Structure

一种有效的差分隐私直方图发布方法是将直方图映射为满d叉区间树或任意k-区间树的形式,然后利用最优线性无偏估计进行一致性修复,提高差分隐私直方图发布数据的区间计数查询精度。但是并非所有直方图都能映射为满d叉区间树,并且任意k-区间树的树形结构不稳定会导致查询精度的波动。在利用直方图进行数据发布的过程中,提出一种基于线段树的树形结构构造方法(Segment-Tree)。方法首先将直方图转换为类似线段树结构的树,然后对其添加噪音,最后对发布优化结果。针对算法所发布数据的区间计数查询精度及算法效率,与同类算法进行了比较分析,结果表明了其可行性和有效性。

An effective differential privacy histogram publishing method is to map the histogram into a full d-inter⁃val tree or an arbitrary k-interval tree.And then basing on BLUE,the consistency constraint of interval tree was used to improve the interval count query precision of data published by differential privacy histogram.However,not all of the histograms can be mapped to a full d-interval tree.Furthermore,the instability of k-interval tree structure can lead to the unstable volatility of query precision.Hence,in the process of using the histogram for data published,a tree structure construction method based on Segment-Tree was proposed.This method first converts the histogram to a binary tree which is similar to Segment-tree,then adds noise to it,and optimizes the release result finally.The exper⁃imental analysis was designed by comparing Segment-Tree and the similar algorithms on the accuracy of range count⁃ing queries and the algorithm efficiency.The result of the Segment-Tree is feasible and effective.