差分隐私下多重一致性约束问题的逼近方法

摘要：

为了解决差分隐私下多重一致性约束的最优发布问题,通过分析最优一致性发布原理提出了多重一致性约束问题的逼近方法.所提方法的主要思想是将一致性约束问题划分为多个一致性约束子问题,通过反复独立地求解各一致性约束子问题实现原问题的最优一致性发布.其优势在于一致性约束问题划分之后,子问题往往更容易求解或者实现子问题最优一致性发布的技术已相当成熟,从而能够解决更加复杂的差分隐私最优发布问题.分析论证了逼近方法的收敛性,保证任意一致性约束子问题的划分均能实现原问题的最优一致性发布.并且,以销量直方图发布为例,基于多重一致性约束问题的逼近方法设计了差分隐私餐馆销量直方图一致性并行发布算法.实验表明,该算法相比通用解法可提升效率高达400倍,并且具备处理百万级大规模数据的能力.

关键词：差分隐私、一致性约束、逼近方法、收敛性、并行计算

所属期刊栏目：42

分类号：TP309(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;国家自然科学基金

在线出版日期：2021-07-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：107-117