Approximation method of multiple consistency constraint under differential privacy - Jianping CAI; Ximeng LIU; Jinbo XIONG; Zuobin YING; Yingjie WU (Tongxin xuebao)
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.