差分隐私二维数据流统计发布

　　0 引言

　　随着网络技术的高速发展，数据流已经普遍存在于各种应用中，例如：在线交易、疾病监控、环境监测等。它们通常表现为高速、连续到达、总量大，且不适合二次存取。在线处理这些数据及实时发布相关统计信息将带来巨大的价值。然而，数据流中包含了许多个人隐私信息，直接对外发布数据将会导致个人隐私泄露。因此，如何在处理数据流和发布数据的过程中，保护数据流中的个人隐私信息是当前一个研究热点。

　　Dwork[1]提出的差分隐私保护模型是公认的较为严格和强健的保护模型。相比k-匿名[2]、l-多样性[3]等模型，该保护模型不关心攻击者所具有的背景知识，即使攻击者已经掌握除某一条记录之外的所有记录的敏感信息，该记录的敏感信息也无法被泄露。近年来，一些研究人员基于差分隐私在数据流领域上取得了若干有价值的研究成果[4-14]。然而，目前的研究成果均针对一维数据流，而现实应用中数据流不仅仅只有一维属性，如何在满足差分隐私的前提下高效率处理多维数据流并兼顾发布数据的可用性具有重要的意义。

　　1 相关工作

　　近年来，研究人员已在差分隐私的模型下对数据流的统计发布进行了一定的研究。文献[4-6]首先提出了面向数据流的差分隐私连续统计与发布方法，这些方法在实现数据流实时统计与相关信息发布的同时保证不泄露个人隐私。文献[7]提出了多种针对二进制数据流的差分隐私统计发布方法，并在此基础上提出能抵抗单一攻击和多个攻击的算法。文献[4-7]的研究成果虽在一定程度上能够很好地保护数据流中的个人隐私不被泄露，然而这些方法主要考虑的是在二进制流背景，即假定数据流元素只取0或1的情况下统计和发布数据流中1出现的次数问题，其应用范围具有一定的局限性。

　　文献[8-10]针对更一般一维数据流展开研究，其中文献[8]针对现有工作中只能固定一种查询的问题，提出基于滑动窗口计数查询的方法。方法首先通过选取部分查询作为代表查询：针对代表查询，算法直接返添加适当噪声后的结果；而对非代表查询，通过分解与组合生成其查询结果。文献[9]在分布式环境下不可信的收集者想要聚集多个用户数据流的统计信息，为保证用户的隐私，提出结合差分隐私保护技术与加密技术的方法来解决分布式环境下的协同聚集问题，从而使数据收集者无法获取除信息总和以外的其他信息。文献[10]则是通过近似统计，并采用滑动窗口和加密技术，有效地在分布式环境下实现对数据流的连续统计发布。

　　现有关于差分隐私数据流统计发布的研究虽已取得一定成果，但均只面向一维数据流。本文拟针对二维数据流，设计出有效的差分隐私统计发布算法，并保证发布数据具有较高的可用性。

　　4.1 算法思想

　　算法的主要思想 针对二维数据流，把滑动窗口N内的数据作为统计发布对象。首先将滑动窗口N个数据依时间顺序依次划分成k个大小为W的不相交窗口单元。对于每个窗口单元分别进行统计过滤；然后通过k个窗口单元的统计结果合并生成滑动窗口N的统计结果；而后通过条件筛选，添加适当的噪声满足差分隐私的要求。滑动窗口以窗口单元为步长滑动，同时发布统计结果从而实现数据流的连续统计发布。

　　5 实验结果与分析

　　本章将从二维数据流统计发布数据可用性进行实验研究。将本文PTDSS算法、PTDSS-SW算法分别在不同的参数取值的情况下进行各自的实验对比。实验采用定义7所提的相对误差作为度量标准，实验结果为多组实验取平均值相对误差的结果。

　　5.1 实验数据与环境

　　实验采用了Netflix数据集，其包含有17770部电影从1999-11-11—2005-12-31被480189个用户的评分记录。通过取2001-01-01—2005-12-31的中的2817100条记录将电影ID和时间分别作为数据流的第一维与第二维属性，并将其作随机排序后作为实验数据。

　　实验环境：Intel Core i3-3210M CPU 3.20GHz，4GB内存，Ubuntu12.04操作系统。采用C语言实现算法，并利用Matlab画出实验图表。

　　5.2 实验结果与分析

　　6 结语

　　本文针对二维数据流统计发布存在隐私泄露问题，提出了满足差分隐私要求的二维数据流统计发布算法：PTDSS算法和PTDSS-SW算法。PTDSS算法在满足差分隐私的要求下，实现固定长度二维数据流的统计发布；PTDSS-SW算法在PTDSS算法的基础上，利用滑动窗口机制实现了二维数据流的连续统计发布。理论分析与实验结果表明，算法可安全地实现二维数据流统计发布的隐私保护，同时保证统计发布结果的可用性较高。