Differentially Private Data Publishing and Analysis: A Survey <s> Transaction Data Publishing <s> We define a new interactive differentially private mechanism --- the median mechanism --- for answering arbitrary predicate queries that arrive online. Given fixed accuracy and privacy constraints, this mechanism can answer exponentially more queries than the previously best known interactive privacy mechanism (the Laplace mechanism, which independently perturbs each query result). With respect to the number of queries, our guarantee is close to the best possible, even for non-interactive privacy mechanisms. Conceptually, the median mechanism is the first privacy mechanism capable of identifying and exploiting correlations among queries in an interactive setting. We also give an efficient implementation of the median mechanism, with running time polynomial in the number of queries, the database size, and the domain size. This efficient implementation guarantees privacy for all input databases, and accurate query results for almost all input distributions. The dependence of the privacy on the number of queries in this mechanism improves over that of the best previously known efficient mechanism by a super-polynomial factor, even in the non-interactive setting. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Transaction Data Publishing <s> We consider statistical data analysis in the interactive setting. In this setting a trusted curator maintains a database of sensitive information about individual participants, and releases privacy-preserving answers to queries as they arrive. Our primary contribution is a new differentially private multiplicative weights mechanism for answering a large number of interactive counting (or linear) queries that arrive online and may be adaptively chosen. This is the first mechanism with worst-case accuracy guarantees that can answer large numbers of interactive queries and is {\em efficient} (in terms of the runtime's dependence on the data universe size). The error is asymptotically \emph{optimal} in its dependence on the number of participants, and depends only logarithmically on the number of queries being answered. The running time is nearly {\em linear} in the size of the data universe. As a further contribution, when we relax the utility requirement and require accuracy only for databases drawn from a rich class of databases, we obtain exponential improvements in running time. Even in this relaxed setting we continue to guarantee privacy for {\em any} input database. Only the utility requirement is relaxed. Specifically, we show that when the input database is drawn from a {\em smooth} distribution — a distribution that does not place too much weight on any single data item — accuracy remains as above, and the running time becomes {\em poly-logarithmic} in the data universe size. The main technical contributions are the application of multiplicative weights techniques to the differential privacy setting, a new privacy analysis for the interactive setting, and a technique for reducing data dimensionality for databases drawn from smooth distributions. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Transaction Data Publishing <s> In this paper we study the problem of approximately releasing the cut function of a graph while preserving differential privacy, and give new algorithms (and new analyses of existing algorithms) in both the interactive and non-interactive settings. ::: ::: Our algorithms in the interactive setting are achieved by revisiting the problem of releasing differentially private, approximate answers to a large number of queries on a database. We show that several algorithms for this problem fall into the same basic framework, and are based on the existence of objects which we call iterative database construction algorithms. We give a new generic framework in which new (efficient) IDC algorithms give rise to new (efficient) interactive private query release mechanisms. Our modular analysis simplifies and tightens the analysis of previous algorithms, leading to improved bounds. We then give a new IDC algorithm (and therefore a new private, interactive query release mechanism) based on the Frieze/Kannan low-rank matrix decomposition. This new release mechanism gives an improvement on prior work in a range of parameters where the size of the database is comparable to the size of the data universe (such as releasing all cut queries on dense graphs). ::: ::: We also give a non-interactive algorithm for efficiently releasing private synthetic data for graph cuts with error O(|V|1.5). Our algorithm is based on randomized response and a non-private implementation of the SDP-based, constant-factor approximation algorithm for cut-norm due to Alon and Naor. Finally, we give a reduction based on the IDC framework showing that an efficient, private algorithm for computing sufficiently accurate rank-1 matrix approximations would lead to an improved efficient algorithm for releasing private synthetic data for graph cuts. We leave finding such an algorithm as our main open problem. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Transaction Data Publishing <s> We consider the problem of privately answering queries defined on databases which are collections of points belonging to some metric space. We give simple, computationally efficient algorithms for answering distance queries defined over an arbitrary metric. Distance queries are specified by points in the metric space, and ask for the average distance from the query point to the points contained in the database, according to the specified metric. Our algorithms run efficiently in the database size and the dimension of the space, and operate in both the online query release setting, and the offline setting in which they must in polynomial time generate a fixed data structure which can answer all queries of interest. This represents one of the first subclasses of linear queries for which efficient algorithms are known for the private query release problem, circumventing known hardness results for generic linear queries. <s> BIB004
The most popular representation of D is a transaction dataset, in which every record represents an individual with d attributes. Query separation. The goal of query separation is to design a separation strategy for given types of queries to decrease noise. Roth BIB001 presented the median mechanism and found that, among any set of m queries, there are Oðlog mlog jX jÞ queries that can determine the answers of all other queries. Based on this observation, all queries are separated into hard and easy queries. Hard queries can be answered directly by the Laplace mechanism, while easy queries are answered by the median values of hard query results. Therefore, easy queries do not consume any privacy budget. By separating the queries, the median mechanism can answer exponentially many more queries with acceptable accuracy; however, it is inefficient and comes with an exponential time complexity corresponding to the dataset size n. Iteration. Hardt et al. BIB002 proposed private multiplicative weights (PMW), which considers datasets as a histogram with positive weight on each bin. By updating the weights, PMW constructs a histogram sequence to answer a set of queries. After the parameters have been calibrated for complexity and accuracy, this mechanism is able to answer each query with a sampling error approximately to Oððlog mÞ= ffiffiffi n p Þ. This means that the sampling error grows logarithmically with an increase in the number of queries being answered, while the Laplace mechanism's error is linear, increasing by m. In addition, PMW can accurately answer an exponential number of queries. Similarly, Gupta et al. BIB003 presented a general iteration framework, termed iterative database construct (IDC), which implements other release mechanisms by using the framework. In each round of iteration, when a significant difference between the current dataset and the original dataset is witnessed for a given query, the mechanism updates the current dataset for the next update. IDC is a more general framework that can be incorporated into various other mechanisms, including PMW and the median. Discussion. The query separation and iteration mechanisms can answer more queries than that of the Laplace mechanism, normally an exponential number of n. With an increase of the number of queries, the error bound of the Laplace mechanism increases by mlog m, whereas other mechanisms limit the increase to log m, which is a huge improvement when searching an entire data universe. With the exception of the Laplace mechanism, most of the other mechanisms are inefficient, as they do need to traverse the whole data universe. Accordingly, the error bound grows logarithmically with jX j in these mechanisms. Given iteration mechanisms outperform others in terms of the error bound, many subsequent works, therefore, have followed the iteration mechanism approach. For example, based on IDC, Huang et al. BIB004 considered the distance query defined over an arbitrary metric. Iteration mechanisms are normally used in low-dimensional datasets or histograms; however, publishing high-dimensional datasets still needs further exploration.