Differentially Private Data Publishing and Analysis: A Survey <s> Batch Query Publishing <s> Privacy-preserving data publishing has attracted considerable research interest in recent years. Among the existing solutions, ∈-differential privacy provides the strongest privacy guarantee. Existing data publishing methods that achieve ∈-differential privacy, however, offer little data utility. In particular, if the output data set is used to answer count queries, the noise in the query answers can be proportional to the number of tuples in the data, which renders the results useless. In this paper, we develop a data publishing technique that ensures ∈-differential privacy while providing accurate answers for range-count queries, i.e., count queries where the predicate on each attribute is a range. The core of our solution is a framework that applies wavelet transforms on the data before adding noise to it. We present instantiations of the proposed framework for both ordinal and nominal data, and we provide a theoretical analysis on their privacy and utility guarantees. In an extensive experimental study on both real and synthetic data, we show the effectiveness and efficiency of our solution. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Batch Query Publishing <s> Prior work in differential privacy has produced techniques for answering aggregate queries over sensitive data in a privacy-preserving way. These techniques achieve privacy by adding noise to the query answers. Their objective is typically to minimize absolute errors while satisfying differential privacy. Thus, query answers are injected with noise whose scale is independent of whether the answers are large or small. The noisy results for queries whose true answers are small therefore tend to be dominated by noise, which leads to inferior data utility. This paper introduces iReduct, a differentially private algorithm for computing answers with reduced relative error. The basic idea of iReduct is to inject different amounts of noise to different query results, so that smaller (larger) values are more likely to be injected with less (more) noise. The algorithm is based on a novel resampling technique that employs correlated noise to improve data utility. Performance is evaluated on an instantiation of iReduct that generates marginals, i.e., projections of multi-dimensional histograms onto subsets of their attributes. Experiments on real data demonstrate the effectiveness of our solution. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Batch Query Publishing <s> We address one-time publishing of non-overlapping counts with e-differential privacy. These statistics are useful in a wide and important range of applications, including transactional, traffic and medical data analysis. Prior work on the topic publishes such statistics with prohibitively low utility in several practical scenarios. Towards this end, we present GS, a method that pre-processes the counts by elaborately grouping and smoothing them via averaging. This step acts as a form of preliminary perturbation that diminishes sensitivity, and enables GS to achieve e-differential privacy through low Laplace noise injection. The grouping strategy is dictated by a sampling mechanism, which minimizes the smoothing perturbation. We demonstrate the superiority of GS over its competitors, and confirm its practicality, via extensive experiments on real datasets. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Batch Query Publishing <s> We describe a new algorithm for answering a given set of range queries under e-differential privacy which often achieves substantially lower error than competing methods. Our algorithm satisfies differential privacy by adding noise that is adapted to the input data and to the given query set. We first privately learn a partitioning of the domain into buckets that suit the input data well. Then we privately estimate counts for each bucket, doing so in a manner well-suited for the given query set. Since the performance of the algorithm depends on the input database, we evaluate it on a wide range of real datasets, showing that we can achieve the benefits of data-dependence on both "easy" and "hard" databases. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Batch Query Publishing <s> Differential privacy is a robust privacy standard that has been successfully applied to a range of data analysis tasks. We describe the matrix mechanism, an algorithm for answering a workload of linear counting queries that adapts the noise distribution to properties of the provided queries. Given a workload, the mechanism uses a different set of queries, called a query strategy, which are answered using a standard Laplace or Gaussian mechanism. Noisy answers to the workload queries are then derived from the noisy answers to the strategy queries. This two-stage process can result in a more complex, correlated noise distribution that preserves differential privacy but increases accuracy. We provide a formal analysis of the error of query answers produced by the mechanism and investigate the problem of computing the optimal query strategy in support of a given workload. We show that this problem can be formulated as a rank-constrained semidefinite program. We analyze two seemingly distinct techniques proposed in the literature, whose similar behavior is explained by viewing them as instances of the matrix mechanism. We also describe an extension of the mechanism in which nonnegativity constraints are included in the derivation process and provide experimental evidence of its efficacy. <s> BIB005 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Batch Query Publishing <s> Differential privacy has recently become very promising in achieving data privacy guarantee. Typically, one can achieve e-differential privacy by adding noise based on Laplace distribution to a query result. To reduce the noise magnitude for higher accuracy, various techniques have been proposed. They generally require high computational complexity, making them inapplicable to large-scale datasets. In this paper, we propose a novel orthogonal mechanism (OM) to represent a query set Q with a linear combination of a new query set Q, where Q consists of orthogonal query sets and is derived by exploiting the correlations between queries in Q. As a result of orthogonality of the derived queries, the proposed technique not only greatly reduces computational complexity, but also achieves better accuracy than the existing mechanisms. Extensive experimental results demonstrate the effectiveness and efficiency of the proposed technique. <s> BIB006 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Batch Query Publishing <s> Differential privacy is a promising privacy-preserving paradigm for statistical query processing over sensitive data. It works by injecting random noise into each query result, such that it is provably hard for the adversary to infer the presence or absence of any individual record from the published noisy results. The main objective in differentially private query processing is to maximize the accuracy of the query results, while satisfying the privacy guarantees. Previous work, notably \cite{LHR+10}, has suggested that with an appropriate strategy, processing a batch of correlated queries as a whole achieves considerably higher accuracy than answering them individually. However, to our knowledge there is currently no practical solution to find such a strategy for an arbitrary query batch; existing methods either return strategies of poor quality (often worse than naive methods) or require prohibitively expensive computations for even moderately large domains. Motivated by this, we propose low-rank mechanism (LRM), the first practical differentially private technique for answering batch linear queries with high accuracy. LRM works for both exact (i.e., $\epsilon$-) and approximate (i.e., ($\epsilon$, $\delta$)-) differential privacy definitions. We derive the utility guarantees of LRM, and provide guidance on how to set the privacy parameters given the user's utility expectation. Extensive experiments using real data demonstrate that our proposed method consistently outperforms state-of-the-art query processing solutions under differential privacy, by large margins. <s> BIB007 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Batch Query Publishing <s> Differential privacy enables organizations to collect accurate aggregates over sensitive data with strong, rigorous guarantees on individuals' privacy. Previous work has found that under differential privacy, computing multiple correlated aggregates as a batch, using an appropriate strategy, may yield higher accuracy than computing each of them independently. However, finding the best strategy that maximizes result accuracy is non-trivial, as it involves solving a complex constrained optimization program that appears to be non-convex. Hence, in the past much effort has been devoted in solving this non-convex optimization program. Existing approaches include various sophisticated heuristics and expensive numerical solutions. None of them, however, guarantees to find the optimal solution of this optimization problem. This paper points out that under (e, ཬ)-differential privacy, the optimal solution of the above constrained optimization problem in search of a suitable strategy can be found, rather surprisingly, by solving a simple and elegant convex optimization program. Then, we propose an efficient algorithm based on Newton's method, which we prove to always converge to the optimal solution with linear global convergence rate and quadratic local convergence rate. Empirical evaluations demonstrate the accuracy and efficiency of the proposed solution. <s> BIB008
Batch query publishing refers to the most common noninteractive scenario in which a fixed set of m queries F ¼ ff 1 ; . . . ; f m g are answered in a batch. Using Table 4 again to show the batch query problem, suppose a curator would like to release a batch of range queries for Table 4 , and Table 7 contains all possible range queries F ¼ ff 1 ; . . . ; f 10 g. Deleting any record in D will change at most 6 query results (column containing x 2 or x 3 in Table 7 ) in F . According to the definition of sensitivity, the sensitivity of F is 6, which is much higher than the sensitivity of a single query. Therefore, most researches focus on how to decrease the sensitivity of F . Transformation. One possible means of decreasing noise is to re-calibrate the sensitivity in a new data structure A. Xiao et al. BIB001 proposed a wavelet transformation, called Privelet, which applies a wavelet transformation on the frequency dataset D to generate a wavelet coefficient A. Each entry of A is considered as a linear combination of the entries in D. Range queries can be generated with a linear combination of basic queries. Table 8 shows the basic queries. For example, the answer of rangeðx 2 ; x 3 Þ ¼ x 2 þ x 3 can be generated by rangeðx 2 ; x 3 Þ ¼ 0:5f 1 À 0:5f 3 À 0:5f 4 , and the sensitivity will be decreased from 6 to 3. In this way, the sensitivity of the wavelet coefficient is estimated as 1 þ log 2 n and the variance of noise per answer is Oððlog 2 nÞ 3 = 2 Þ, which is much smaller than that in the Laplace mechanism. Li et al. BIB004 proposed a matrix mechanism which can answer sets of linear counting queries. The set of queries, defined as a workload, is transformed into a matrix A, where each row contains the coefficients of a linear query. The essential element of the matrix mechanism is to select A to represent the set of queries. Based on the selection of A, the matrix mechanism can be extended to a variety of approaches. For example, if A is an identity matrix, this mechanism can be considered to be a normal Laplace mechanism for batch queries. If A is selected using a Haar wavelet, it can be extended as a Privelet BIB001 . The error bound of the matrix mechanism was analyzed in their subsequent paper BIB005 . They proved that when batch queries are denoted in a matrix manner, the minimum error for the result can be evaluated according to the spectral properties of this query matrix. Similarly, Huang et al. BIB006 transformed the query sets into a set of orthogonal queries to reduce the correlation between queries. Yuan et al. BIB007 formulated searches of A as a constrained optimization problem. This approach is challenging, however, as the optimization objective is nonconvex. They formulated searches of A as a low-rank matrix  factorization problem using an iteration method to approximate a suitable A. Later, they considered approximate differential privacy and transformed the optimization objective into a convex program to minimize the overall error in the results BIB008 . Dataset partitioning. Kellaris et al. BIB003 decomposed the dataset columns into disjoint groups and added Laplace noise to these groups' counts. The final result is generated using the new column count. Because the maximum number of original counts in a group affected by a user is limited, the sensitivity of each group is decreased, and the Laplace noise required for -differential privacy also diminishes. The advantage of this mechanism is that it can limit the sensitivity for numerical datasets. Iteration. Iteration has also been used in the batch query publishing. By recursively approximating the true answer, the noise in the output can be effectively diminished. Xiao et al. BIB002 aimed to decrease errors in the released output. They argued that the Laplace mechanism adds noise with a constant range to every query answer without considering the true value of the answer. Thus, queries with small answers have a much higher error than expected, defined as relative error. In practice, larger answers can tolerate more noise. In some applications, relative errors are more important than absolute errors. To decrease the relative error, Xiao et al. BIB002 proposed a mechanism named iReduct, which initially obtains rough error estimations for query answers and subsequently uses this information to iteratively refine these error evaluations. Discussion. The key problem in batch query publishing is how to decrease the sensitivity between correlated queries. Currently, transformation is the most popular way to tackle this problem. Current works mainly focus on range queries and develop appropriate structures to answer linear combinations of those queries. More types of structures need to be developed to answer various types of queries. Iteration or partitioning the dataset may not be effective for correlation decomposition, but they have the potential to answer more types of queries.