摘要
为了解决差分隐私下多重一致性约束的最优发布问题,通过分析最优一致性发布原理提出了多重一致性约束问题的逼近方法。所提方法的主要思想是将一致性约束问题划分为多个一致性约束子问题,通过反复独立地求解各一致性约束子问题实现原问题的最优一致性发布。其优势在于一致性约束问题划分之后,子问题往往更容易求解或者实现子问题最优一致性发布的技术已相当成熟,从而能够解决更加复杂的差分隐私最优发布问题。分析论证了逼近方法的收敛性,保证任意一致性约束子问题的划分均能实现原问题的最优一致性发布。并且,以销量直方图发布为例,基于多重一致性约束问题的逼近方法设计了差分隐私餐馆销量直方图一致性并行发布算法。实验表明,该算法相比通用解法可提升效率高达400倍,并且具备处理百万级大规模数据的能力。
Under differential privacy,to solve the optimal publishing problem with multiple consistency constraints,an approximation method of multiple consistency constraints was proposed by the theoretical analysis of the principle of optimal consistency release.The main idea was to divide the consistency constraint problem into several consistency constraint sub-problems and then achieve the original problem's optimal consistency release by solving each consistency constraint sub-problem repeatedly and independently.The advantage was that after the consistency constraint problem divided,the sub-problems were often easier to solve,or the technology to achieve optimal and consistent release of sub-problems is quite mature.Therefore more complex differential privacy optimal release problem could be solved.After analysis,the approximation method's convergence was fully demonstrated,ensuring that any partition of consistency constrained sub-problems can always achieve the optimal consistency release of the original problem.Furthermore,taking the sales histogram publishing as an example,based on the approximation method of multiple consistency constraints,a parallel algorithm was designed with optimal consistency release under differential privacy.The experimental results show that the algorithm's efficiency is 400 times higher than that of the general solution,and the algorithm can process millions of large-scale data.
作者
蔡剑平
刘西蒙
熊金波
应作斌
吴英杰
CAI Jianping;LIU Ximeng;XIONG Jinbo;YING Zuobin;WU Yingjie(College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China;College of Mathematics and Informatics,Fujian Normal University,Fuzhou 350117,China;School of Electrical and Electronic Engineering,Nanyang Technological University,Singapore 639798,Singapore)
出处
《通信学报》
EI
CSCD
北大核心
2021年第6期107-117,共11页
Journal on Communications
基金
国家自然科学基金资助项目(No.62072109,No.U1804263,No.61702105,No.62002062)。
关键词
差分隐私
一致性约束
逼近方法
收敛性
并行计算
differential privacy
consistency constraint
approximation method
convergence
parallel computing
