异方差加噪下的差分隐私直方图发布算法

现有基于区间树结构的差分隐私直方图发布方法大多采用同方差加噪方式,对其进一步研究发现,采用异方差加噪策略可以进一步提升发布直方图的区间计数查询精度,然而当前基于异方差加噪的差分隐私直方图发布方法对区间树结构却有严格的要求,导致灵活性与实用性较低。为此,提出了一种异方差加噪下面向任意区间树结构的差分隐私直方图发布算法LUE-DPTree(inear unbiased estimator for differential private tree)。首先根据区间计数查询的分布,计算区间树中节点的覆盖概率,并据此分配隐私预算,实现异方差加噪;接着经分析指出该异方差加噪策略适用于任意区间树结构,且从理论上证明了在任意区间树结构下进行异方差加噪后,仍可在一致性约束下利用最优线性无偏估计进一步降低区间计数查询的误差。针对算法的区间计数查询精度及执行效率,与同类算法进行了比较分析。实验结果表明,LUE-DPTree算法是有效可行的。

异方差加噪下差分隐私流数据发布一致性优化算法

现有基于树结构的差分隐私流数据统计发布方法未能充分利用统计查询可能存在的特定分布规律而进一步提升发布流数据的精度,为此,该文提出滑动窗口下基于异方差加噪的差分隐私流数据发布算法。首先动态构建滑动窗口内流数据对应的差分隐私区间树;其次根据统计查询分布规律计算树节点的覆盖概率,据此对树节点的隐私预算及树结构参数进行调整,以实现异方差加噪;最后,针对异方差加噪后区间树节点值可能不满足一致性约束的问题,设计实时的一致性调节策略。实验结果表明:与同类算法相比,该算法具有较高的查询精度及算法效率。

差分隐私保护BIRCH算法

针对现有的层次聚类算法可能存在的隐私数据泄露问题,提出一个面向大规模数据集,且有效保护用户隐私的差分隐私BIRCH算法DP-BIRCH.DP-BIRCH算法依据差分隐私模型并借鉴概率分配思想,基于误差最小原则来调整隐私预算,采用异方差加噪方式,对待发布的CF树加入Laplace噪音.为进一步提高算法的查询精度及可用性,在DP-BIRCH算法的基础上,提出FP-BIRCH算法,同时采用线性回归及迭代运算等方法,解决了DP-BIRCH算法中存在的不一致约束性问题.实验采用两组真实数据集,在不同的隐私预算下,对DP-BIRCH算法和FP-BIRCH算法发布的DP-CF树与FP-CF树进行查询误差比较.实验结果表明,相比DP-BIRCH算法,所提出的FP-BIRCH算法有效可行,且查询精度更高.

差分隐私流数据自适应发布算法

当前,许多实际应用需要持续地对流数据进行发布,现有关于单条流数据的差分隐私发布研究大多考虑区间的累和发布,而现实应用中往往需要对发布流数据进行任意区间计数查询,同时,用户查询往往存在特定规律,可针对历史查询进行自适应统计与分析,提高发布数据可用性.为此,提出一个基于历史查询的差分隐私流数据自适应发布算法HQ_DPSAP.算法HQ_DPSAP首先结合流数据的特性,利用滑动窗口机制动态构建窗口内流数据对应的差分隐私区间树,而后进一步分析与计算树节点的覆盖概率;接着自底向上计算隐私分配参数,再自顶向下分配隐私预算,并据此对树节点进行异方差加噪;最后根据历史查询规律自适应调整树节点的隐私预算与树结构参数,以实现流数据的自适应发布.实验对算法HQ_DPSAP的可行性及有效性进行比较分析,结果表明:算法HQ_DPSAP可有效支持任意区间计数查询,且具有较低的查询均方误差和较高的算法执行效率.