论文部分内容阅读
随着信息技术高速发展,数据流已经越来越广泛的出现在众多的网络应用程序中。数据流具有速度快,到达时间连续,总容量大等一系列特点。因此一般要求数据流处理算法在单遍扫描的限制条件下就可以得到计算结果。在线处理这些数据流,并且能够对相关数据统计信息进行实时发布,这会带来巨大商业应用价值。然而,数据流中包含了大量的个人隐私信息,如果把这些数据直接进行发布的话,会造成用户个人隐私信息的泄露。我们通过以下两个例子说明:(1)在实时交通信息系统分析中,个人所规划的目的地信息遭到暴露;(2)在医疗分析数据集中,患者的患病信息遭到泄露。这些关系个人位置信息以及个人患病信息的数据都是非常重要的信息,因此,如何在众多的应用中,实时的发布数据并实现隐藏用户的隐私数据已成为重要的研究问题。目前虽然存在着众多的针对静态数据集的直方图发布方法,然而这些方法由于需要缓存数据流中滑动窗口的全部数据而无法有效的快速处理数据流。另一方面,虽然现在已经有一些专门针对数据流滑动窗口直方图发布方法,但是现有这些方法用来处理滑动窗口模型时,会产生如下两个问题:(1)没有考虑利用直方图发布问题和滑动窗口近似统计问题之间的相关性;(2)没有考虑数据流近似技术对于数据隐私保护的作用,而仅选择保存当前窗口内所有数据生成的直方图进行简单加噪处理。针对于以上两个问题,本文主要从以下两个方面开展了工作:1:提出了一种基于相关距离数据流差分隐私直方图发布算法HPA-SW(Histogram Publishing Algorithm for Sliding Window Model)。该算法首先利用近似统计的思想来将一个滑动窗口划分成k个子块,并通过调整k的大小来调整数据的近似统计误差;然后,利用相似性度量的方法计算相邻时刻的统计数据相似距离,通过比较相似距离和阈值之间的差异优化隐私预算。通过理论和实验证明,该算法高效处理数据流中的数据而达到用户满意的发布误差。HPA-SW算法从实验上表明比现有最好的算法降低了50%。2:针对在实际应用中存在数据可用性低和隐私泄露问题,提出了优化算法AHPM-SW(Adaptive Histogram Publishing Method for Sliding Window)。AHPM-SW算法首先利用数据流近似计数方法来预测下一时刻滑动窗口内数据的分布信息;再通过比较估计值与真实值的之间的差异来选取合适的发布值;最后对排序后的直方图进行聚类处理并优化其桶内数据的误差。最后通过理论与实验证明AHPM-SW算法具有一定的可用性。标准数据集合上的测试结果显示:AHPM-SW算法比现有最好的基于分组的直方图发布算法,平均发布误差减小了约77%。