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

摘要

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