Differentially Private Data Publishing and Analysis: A Survey <s> Summary of the Non-Interactive Setting <s> Privacy-preserving data publishing is an important problem that has been the focus of extensive study. The state-of-the-art solution for this problem is differential privacy, which offers a strong degree of privacy protection without making restrictive assumptions about the adversary. Existing techniques using differential privacy, however, cannot effectively handle the publication of high-dimensional data. In particular, when the input dataset contains a large number of attributes, existing methods require injecting a prohibitive amount of noise compared to the signal in the data, which renders the published data next to useless. To address the deficiency of the existing methods, this paper presents P riv B ayes , a differentially private method for releasing high-dimensional data. Given a dataset D, P riv B ayes first constructs a Bayesian network N, which (i) provides a succinct model of the correlations among the attributes in D and (ii) allows us to approximate the distribution of data in D using a set P of low-dimensional marginals of D. After that, P riv B ayes injects noise into each marginal in P to ensure differential privacy and then uses the noisy marginals and the Bayesian network to construct an approximation of the data distribution in D. Finally, P riv B ayes samples tuples from the approximate distribution to construct a synthetic dataset, and then releases the synthetic data. Intuitively, P riv B ayes circumvents the curse of dimensionality, as it injects noise into the low-dimensional marginals in P instead of the high-dimensional dataset D. Private construction of Bayesian networks turns out to be significantly challenging, and we introduce a novel approach that uses a surrogate function for mutual information to build the model more accurately. We experimentally evaluate P riv B ayes on real data and demonstrate that it significantly outperforms existing solutions in terms of accuracy. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Summary of the Non-Interactive Setting <s> Releasing high-dimensional data enables a wide spectrum of data mining tasks. Yet, individual privacy has been a major obstacle to data sharing. In this paper, we consider the problem of releasing high-dimensional data with differential privacy guarantees. We propose a novel solution to preserve the joint distribution of a high-dimensional dataset. We first develop a robust sampling-based framework to systematically explore the dependencies among all attributes and subsequently build a dependency graph. This framework is coupled with a generic threshold mechanism to significantly improve accuracy. We then identify a set of marginal tables from the dependency graph to approximate the joint distribution based on the solid inference foundation of the junction tree algorithm while minimizing the resultant error. We prove that selecting the optimal marginals with the goal of minimizing error is NP-hard and, thus, design an approximation algorithm using an integer programming relaxation and the constrained concave-convex procedure. Extensive experiments on real datasets demonstrate that our solution substantially outperforms the state-of-the-art competitors. <s> BIB002
High sensitivity presents a big challenge in non-interactive settings. Batch query publishing methods can only publish limited types of queries. Publishing a synthetic dataset seems appealing because, in some scenarios, people require details of the attributes to determine further analysis methods. The research on synthetic data publishing, however, is still in its early stages and there are many open problems in this area. The essential problem is efficiency. Given most publishing mechanisms need to sample datasets from the entire data universe, it is hard to search for a suitable dataset in polynomial time. Another problem is that synthetic dataset publishing can only publish datasets for particular purposes. For example, an anonymization dataset focuses on a decision tree algorithm, the published dataset obtains an acceptable result for decision tree tasks, yet the proposed method does not guarantee the performance for other types of tasks. Learning-based methods have the same disadvantage, or worse, as they only guarantee learning performance for a particular class. Publishing a dataset for multiple purposes needs further investigation. The third problem is dealing with high-dimensional datasets. Even though BIB001 and BIB002 have undertaken some initial work, they both consume too much of the privacy budget when building the distribution model, making the results less accurate than that of lower-dimensional datasets.