论文摘要
随着科学技术的飞速发展,隐私保护成为一个重要性与日俱增的话题。许多机构拥有海量包含用户敏感信息的数据,发布这些数据具有很高的研究价值,然而可能对个人隐私信息造成威胁。如何保证发布数据既是可用的,又不会泄露数据中所包含个体的隐私信息成了近年来非常热门的研究课题。现有的许多隐私保护机制都忽视攻击者可能拥有背景知识,或者局限于保护某一类型的攻击。为了加强发布数据时对用户隐私的保护,Dwork等人提出了更强的隐私保护机制——微分隐私。利用微分隐私机制发布数据时,即使面对拥有数据库背景知识的攻击者,亦能保护数据库中个体的隐私。论文主要针对若干基于微分隐私的统计数据发布问题进行研究,力图设计出兼顾数据隐私安全和数据可用性的高效数据发布算法。论文的主要工作包括：(1)针对稀疏数据,设计出一个基于桶划分的高效微分隐私数据发布算法。算法利用贪心策略快速寻找出合理的桶划分方案,并用红黑树对算法中最邻近桶的查询和合并进行优化。与现有基于桶划分的算法相比,实验结果表明本文算法能在数据质量没有明显降低的同时有效提高数据发布的效率。(2)针对现有的微分隐私方法在处理较大区间统计查询时,存在查询结果精度过低的问题,提出一种基于“k叉平均树”的噪声添加模型。模型通过将原数据转化成一棵“k叉平均树”,然后对树上的每个节点添加噪声,最后利用公式从“k叉平均树”中导出发布数据。论文还对使查询结果的噪声方差上界最小的最优k取值进行分析,并从理论上证明k取值最优时,采用本文算法所导致的噪声方差上界比现有算法更小。基于固定区间大小和随机区间大小的两类区间统计查询实验对比结果表明,文中算法可有效提高查询结果的精度。(3)将一维区间查询中采用的基于“k叉平均树”的噪声添加模型拓展到多维的情形,以解决多维组合查询存在查询精度不高的问题。其基本思想是先顺序以每一维为核心,将多维拆成多个一维分别构建“k叉平均树”,然后分别添加噪声,最后逆序以每一维为核心,将多维拆成多个一维分别利用公式从“k叉平均树”导出发布数据。基于合成数据和真实数据的实验结果表明,文中算法可有效提高多维组合查询的精度。