Differentially Private Data Publishing and Analysis: A Survey <s> Algorithm 1. Basic k-Means Algorithm <s> We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a database, a query consists of a pair (S, f) where S is a set of rows in the database and f is a function mapping database rows to {0, 1}. The true answer is Σ ieS f(d i ), and a noisy version is released as the response to the query. Results of Dinur, Dwork, and Nissim show that a strong form of privacy can be maintained using a surprisingly small amount of noise -- much less than the sampling error -- provided the total number of queries is sublinear in the number of database rows. We call this query and (slightly) noisy reply the SuLQ (Sub-Linear Queries) primitive. The assumption of sublinearity becomes reasonable as databases grow increasingly large.We extend this work in two ways. First, we modify the privacy analysis to real-valued functions f and arbitrary row types, as a consequence greatly improving the bounds on noise required for privacy. Second, we examine the computational power of the SuLQ primitive. We show that it is very powerful indeed, in that slightly noisy versions of the following computations can be carried out with very few invocations of the primitive: principal component analysis, k means clustering, the Perceptron Algorithm, the ID3 algorithm, and (apparently!) all algorithms that operate in the in the statistical query learning model [11]. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Algorithm 1. Basic k-Means Algorithm <s> We introduce a new, generic framework for private data analysis.The goal of private data analysis is to release aggregate information about a data set while protecting the privacy of the individuals whose information the data set contains.Our framework allows one to release functions f of the data withinstance-based additive noise. That is, the noise magnitude is determined not only by the function we want to release, but also bythe database itself. One of the challenges is to ensure that the noise magnitude does not leak information about the database. To address that, we calibrate the noise magnitude to the smoothsensitivity of f on the database x --- a measure of variabilityof f in the neighborhood of the instance x. The new frameworkgreatly expands the applicability of output perturbation, a technique for protecting individuals' privacy by adding a smallamount of random noise to the released statistics. To our knowledge, this is the first formal analysis of the effect of instance-basednoise in the context of data privacy. Our framework raises many interesting algorithmic questions. Namely,to apply the framework one must compute or approximate the smoothsensitivity of f on x. We show how to do this efficiently for several different functions, including the median and the cost ofthe minimum spanning tree. We also give a generic procedure based on sampling that allows one to release f(x) accurately on manydatabases x. This procedure is applicable even when no efficient algorithm for approximating smooth sensitivity of f is known orwhen f is given as a black box. We illustrate the procedure by applying it to k-SED (k-means) clustering and learning mixtures of Gaussians. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Algorithm 1. Basic k-Means Algorithm <s> Privacy Integrated Queries (PINQ) is an extensible data analysis platform designed to provide unconditional privacy guarantees for the records of the underlying data sets. PINQ provides analysts with access to records through an SQL-like declarative language (LINQ) amidst otherwise arbitrary C# code. At the same time, the design of PINQ's analysis language and its careful implementation provide formal guarantees of differential privacy for any and all uses of the platform. PINQ's guarantees require no trust placed in the expertise or diligence of the analysts, broadening the scope for design and deployment of privacy-preserving data analyses, especially by privacy nonexperts. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Algorithm 1. Basic k-Means Algorithm <s> It is often highly valuable for organizations to have their data analyzed by external agents. However, any program that computes on potentially sensitive data risks leaking information through its output. Differential privacy provides a theoretical framework for processing data while protecting the privacy of individual records in a dataset. Unfortunately, it has seen limited adoption because of the loss in output accuracy, the difficulty in making programs differentially private, lack of mechanisms to describe the privacy budget in a programmer's utilitarian terms, and the challenging requirement that data owners and data analysts manually distribute the limited privacy budget between queries. This paper presents the design and evaluation of a new system, GUPT, that overcomes these challenges. Unlike existing differentially private systems such as PINQ and Airavat, it guarantees differential privacy to programs not developed with privacy in mind, makes no trust assumptions about the analysis program, and is secure to all known classes of side-channel attacks. GUPT uses a new model of data sensitivity that degrades privacy of data over time. This enables efficient allocation of different levels of privacy for different user applications while guaranteeing an overall constant level of privacy and maximizing the utility of each application. GUPT also introduces techniques that improve the accuracy of output while achieving the same level of privacy. These approaches enable GUPT to easily execute a wide variety of data analysis programs while providing both utility and privacy. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Algorithm 1. Basic k-Means Algorithm <s> epsilon-differential privacy is rapidly emerging as the state-of-the-art scheme for protecting individuals' privacy in published analysis results over sensitive data. The main idea is to perform random perturbations on the analysis results, such that any individual's presence in the data has negligible impact on the randomized results. This paper focuses on analysis tasks that involve model fitting, i.e., finding the parameters of a statistical model that best fit the dataset. For such tasks, the quality of the differentially private results depends upon both the effectiveness of the model fitting algorithm, and the amount of perturbations required to satisfy the privacy guarantees. Most previous studies start from a state-of-the-art, non-private model fitting algorithm, and develop a differentially private version. Unfortunately, many model fitting algorithms require intensive perturbations to satisfy -differential privacy, leading to poor overall result quality. Motivated by this, we propose PrivGene, a general-purpose differentially private model fitting solution based on genetic algorithms (GA). PrivGene needs significantly less perturbations than previous methods, and it achieves higher overall result quality, even for model fitting tasks where GA is not the first choice without privacy considerations. Further, PrivGene performs the random perturbations using a novel technique called the enhanced exponential mechanism, which improves over the exponential mechanism by exploiting the special properties of model fitting tasks. As case studies, we apply PrivGene to three common analysis tasks involving model fitting: logistic regression, SVM classification, and k-means clustering. Extensive experiments using real data confirm the high result quality of PrivGene, and its superiority over existing methods. <s> BIB005 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Algorithm 1. Basic k-Means Algorithm <s> Subspace clustering is an unsupervised learning problem that aims at grouping data points into multiple "clusters" so that data points in a single cluster lie approximately on a low-dimensional linear subspace. It is originally motivated by 3D motion segmentation in computer vision, but has recently been generically applied to a wide range of statistical machine learning problems, which often involves sensitive datasets about human subjects. This raises a dire concern for data privacy. In this work, we build on the framework of differential privacy and present two provably private subspace clustering algorithms. We demonstrate via both theory and experiments that one of the presented methods enjoys formal privacy and utility guarantees; the other one asymptotically preserves differential privacy while having good performance in practice. Along the course of the proof, we also obtain two new provable guarantees for the agnostic subspace clustering and the graph connectivity problem which might be of independent interests. <s> BIB006
Require: points r 1 , ...,r n . Ensure: k centers fn 1 ; . . . ; n k g with arranged points repeat 1. Create k clusters by assigning each point to its closest center; 2. Re-calculate the center of each cluster; until centers do not change A basic k-means algorithm is formulated by Algorithm 1. The aim of differential privacy clustering is to add uncertainty into the center n and the number of records in each center. To achieve this goal, noise is added in Step 1 in Algorithm 1. In fact, adding noise to cluster centers is impractical because the sensitivity of the cluster center will be quite large as deleting one point will totally change the center. Therefore, the challenge for clustering is to evaluate and minimize the sensitivity of the cluster centers. Nissim et al. BIB002 used local sensitivity with k-means clustering to circumvent the large sensitivity problem, by relying on the following intuition. In a well-clustered scenario, a point with noise should have approximately the same center as its previous center. In addition, moving a few "wellclustered" records would not ultimately change the centers. As such, they define a local sensitivity to measure the record- based sensitivity of the cluster center, which is much lower than the traditional global sensitivity. Since the value of local sensitivity is difficult to measure, they provide a sample aggregate method to approximate local sensitivity. Based on local sensitivity, Wang et al. BIB006 implemented subspace clustering algorithms. They introduce Laplace mechanism into an agnostic k-means clustering, and an exponential mechanism into Gibbs sampling subspace clustering algorithm. Their subsequent paper,  adopted a Johnson-Lindenstrauss transform to guarantee differential privacy in a subspace clustering algorithm. The JohnsonLindenstrauss transform can reduces the dimensions of the dataset, making the clustering problem practical, as well as preserving the distance between each record. Discussion. In general, even some differentially private platforms such as SuLQ BIB001 , PINQ BIB003 , Privgene BIB005 , Gupt BIB004 can automatically implement clustering algorithms. They all assume that the sensitivity of the cluster centers has been predefined. Even though local sensitivity can partially solve the problem, further reducing sensitivity still remains a challenge. We use Table 12 to illustrate the advantages and disadvantages of local sensitivity and Johnson-Lindenstrauss transform.