Differential Privacy Release Algorithm Based On Set Covering Improvement

With the advent of big data era,data releasing and sharing has become an important link both in scientific research and information industry.In the scenario with privacy protection requirements,the differential privacy model is widely used because it has the advantage of not needing attack hypothesis,not limiting the background knowledge of the attacker,and being able to quantify and analyze the privacy risk.But,current algorithms for the private releasing of multi-dimensional datasets have blindness in privacy protection and low data usability due to too much noise in the query middleware.In view of this issue,we propose algorithms based on regular and irregular marginal tables of frequent item sets to preserve privacy and promote usability.The core of the publishing algorithm based on regular marginal tables is to reduce the dimension of the dataset with the covering set of the same-dimensional marginal tables,and to realize differential privacy protection with Laplace noise.This paper proposes an improvement on the marginal table covering set screening process of the existing marginal table algorithm.With set cover,we model the query combination problem of marginal table,analyze practical the data set with frequent items,and establish a weighted marginal table set cover model with the support value as the weight.By considering the effectiveness of coverage and query combination,a marginal table covering algorithm based on frequent items is proposed,and a regular marginal table covering set with higher data availability is obtained.Aiming at the application scenario with requirement of low data privacy protectable availability and high coverage,a differential privacy model with irregular marginal table partitioning is proposed.With the near-optimal marginal table covering algorithm,the marginal table query coverage set which satisfies the multi-level query policy constraint is found,and the balance privacy protection and data availability.The experimental results show that the two differential privacy publishing algorithms we propose can achieve high efficiency and improve data availability in the multi-dimensional environment by comparison with the existing differential privacy models.