关键词:
差分隐私
连接聚集查询
敏感度
草图
混洗模型
摘要:
随着大数据技术和云计算的广泛应用,信息系统中存储记录的数据量呈爆炸式增长。这些大规模数据为诸多研究机构以及政府决策部门的分析提供了极大便利,但随之而来在数据共享和发布中的隐私泄露问题也日益突出。差分隐私作为一个严格的隐私保护框架,能够有效抵御背景知识攻击,被广泛应用于隐私保护数据发布和挖掘、机器学习和社交网络分析等领域。然而,随着当今的数据库分析任务多样性提高,查询结构也变得更加复杂。现有差分隐私相关研究大多集中在简单数据统计任务,如频率估计、均值估计和频繁项挖掘上,针对复杂连接查询的隐私保护相关工作较为有限。连接聚集查询作为一种常见的数据分析操作,通常涉及多个数据表的连接与聚合计算。其在揭示数据关联价值的同时,除了面临着隐私泄露的风险外,往往还存在查询准确性与效率方面的权衡问题。因此,本文围绕差分隐私下连接聚集查询隐私保护的准确性与效率问题,开展了以下三方面的研究:
(1)针对中心化差分隐私下连接聚集查询敏感度计算时间开销高的问题,本文提出了基于二维fast-AGMS草图的SSE算法。敏感度是差分隐私中调节噪声强度的核心参数,在连接聚集查询时常面临无界敏感度或难以计算的问题。本文提出的SSE算法通过数据压缩实现了高效准确地敏感度计算,提高了实时交互式隐私保护系统的可用性。文中通过详细的理论分析证明了SSE算法的隐私性和误差界。实验验证表明,算法在隐私保护和准确性之间取得了较好的平衡,能够在保证差分隐私的同时,维持较高的准确性。SSE算法极大提高了隐私保护查询的效率,相对于精确计算残差敏感度的方法可提升31%左右,并在复杂连接查询中具有更显著的效果,效率提升达到了56.2%。
(2)针对本地化差分隐私下连接聚集查询由于数据值域较大以及草图哈希冲突引入的误差导致效用低的问题,本文提出了两种基于草图的方法,分别是LDPJoin Sketch和LDPJoin Sketch+,用于在本地化差分隐私下实现高效准确的连接大小估计,并且通过哈达玛变换实现了极低的通信成本。后者基于本文提出的频率感知的扰动协议FAP,在保证隐私的同时,实现了对高频项和低频项数据的高效准确分离,降低了构建草图时的哈希冲突误差,提高了估计效用。通过严格的理论分析和充分的实验证明,所提出方法可以适用于处理在数据域较大的数据集上进行连接聚集查询的情况,并且改进的算法LDPJoin Sketch+提高了本地化差分隐私在高偏度数据上的估计准确性。
(3)针对中心化差分隐私下的隐私信任问题和本地化差分隐私下对噪声要求高的问题,本文提出了混洗差分隐私模型下的连接大小估计效用优化方法SDPJoin Sketch和SDPJoin Sketch+。与本地化差分隐私方法相比,SDPJoin Sketch通过引入洗牌机制减少了噪声,从而提供了更高的效用。并且本文通过形式化证明了该方法在隐私放大方面的优势,量化了效用提升的程度。另外,改进的SDPJoin Sketch+算法通过减少草图构建中的哈希碰撞误差来提高连接大小估计的精度。其采用安全加密技术保护频率属性,而不是直接添加噪声,从而有效提升了效用。大量实验证明,SDPJoin Sketch和SDPJoin Sketch+在连接大小估计任务中,尤其是面对真实和高偏度合成数据集时,相比本地化差分隐私方法具有更好的效用,同时保持了强隐私保护。