Differentially Private Data Publishing and Analysis: A Survey <s> Query separation <s> Recent differentially private query mechanisms offer strong privacy guarantees by adding noise to the query answer. For a single counting query, the technique is simple, accurate, and provides optimal utility. However, analysts typically wish to ask multiple queries. In this case, the optimal strategy is not apparent, and alternative query strategies can involve difficult trade-offs in accuracy, and may produce inconsistent answers. In this work we show that it is possible to significantly improve accuracy for a general class of histogram queries. Our approach carefully chooses a set of queries to evaluate, and then exploits consistency constraints that should hold over the noisy output. In a post-processing phase, we compute the consistent input most likely to have produced the noisy output. The final output is both private and consistent, but in addition, it is often much more accurate. We apply our techniques to real datasets and show they can be used for estimating the degree sequence of a graph with extreme precision, and for computing a histogram that can support arbitrary range queries accurately. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Query separation <s> Differential privacy (DP) is a promising scheme for releasing the results of statistical queries on sensitive data, with strong privacy guarantees against adversaries with arbitrary background knowledge. Existing studies on differential privacy mostly focus on simple aggregations such as counts. This paper investigates the publication of DP-compliant histograms, which is an important analytical tool for showing the distribution of a random variable, e.g., hospital bill size for certain patients. Compared to simple aggregations whose results are purely numerical, a histogram query is inherently more complex, since it must also determine its structure, i.e., the ranges of the bins. As we demonstrate in the paper, a DP-compliant histogram with finer bins may actually lead to significantly lower accuracy than a coarser one, since the former requires stronger perturbations in order to satisfy DP. Moreover, the histogram structure itself may reveal sensitive information, which further complicates the problem. Motivated by this, we propose two novel mechanisms, namely NoiseFirst and StructureFirst, for computing DP-compliant histograms. Their main difference lies in the relative order of the noise injection and the histogram structure computation steps. NoiseFirst has the additional benefit that it can improve the accuracy of an already published DP-compliant histogram computed using a naive method. For each of proposed mechanisms, we design algorithms for computing the optimal histogram structure with two different objectives: minimizing the mean square error and the mean absolute error, respectively. Going one step further, we extend both mechanisms to answer arbitrary range queries. Extensive experiments, using several real datasets, confirm that our two proposals output highly accurate query answers and consistently outperform existing competitors. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Query separation <s> In recent years, many approaches to differentially privately publish histograms have been proposed. Several approaches rely on constructing tree structures in order to decrease the error when answer large range queries. In this paper, we examine the factors affecting the accuracy of hierarchical approaches by studying the mean squared error (MSE) when answering range queries. We start with one-dimensional histograms, and analyze how the MSE changes with different branching factors, after employing constrained inference, and with different methods to allocate the privacy budget among hierarchy levels. Our analysis and experimental results show that combining the choice of a good branching factor with constrained inference outperform the current state of the art. Finally, we extend our analysis to multi-dimensional histograms. We show that the benefits from employing hierarchical methods beyond a single dimension are significantly diminished, and when there are 3 or more dimensions, it is almost always better to use the Flat method instead of a hierarchy. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Query separation <s> In statistical privacy, utility refers to two concepts: information preservation -- how much statistical information is retained by a sanitizing algorithm, and usability -- how (and with how much difficulty) does one extract this information to build statistical models, answer queries, etc. Some scenarios incentivize a separation between information preservation and usability, so that the data owner first chooses a sanitizing algorithm to maximize a measure of information preservation and, afterward, the data consumers process the sanitized output according to their needs [22, 46]. We analyze a variety of utility measures and show that the average (over possible outputs of the sanitizer) error of Bayesian decision makers forms the unique class of utility measures that satisfy three axioms related to information preservation. The axioms are agnostic to Bayesian concepts such as subjective probabilities and hence strengthen support for Bayesian views in privacy research. In particular, this result connects information preservation to aspects of usability -- if the information preservation of a sanitizing algorithm should be measured as the average error of a Bayesian decision maker, shouldn't Bayesian decision theory be a good choice when it comes to using the sanitized outputs for various purposes? We put this idea to the test in the unattributed histogram problem where our decision- theoretic post-processing algorithm empirically outperforms previously proposed approaches. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Query separation <s> When analyzing data that has been perturbed for privacy reasons, one is often concerned about its usefulness. Recent research on differential privacy has shown that the accuracy of many data queries can be improved by post-processing the perturbed data to ensure consistency constraints that are known to hold for the original data. Most prior work converted this post-processing step into a least squares minimization problem with customized efficient solutions. While improving accuracy, this approach ignored the noise distribution in the perturbed data. In this paper, to further improve accuracy, we formulate this post-processing step as a constrained maximum likelihood estimation problem, which is equivalent to constrained L1 minimization. Instead of relying on slow linear program solvers, we present a faster generic recipe (based on ADMM) that is suitable for a wide variety of applications including differentially private contingency tables, histograms, and the matrix mechanism (linear queries). An added benefit of our formulation is that it can often take direct advantage of algorithmic tricks used by the prior work on least-squares post-processing. An extensive set of experiments on various datasets demonstrates that this approach significantly improve accuracy over prior work. <s> BIB005
Only need to add noise to small numbers of queries Some queries do not consume privacy budget, so the mechanism can answer more queries with a fixed privacy budget. Separating queries is a difficult problem Dataset partitioning. As the number of bins is derived from the partition of attribute values, one method for decreasing error is to optimize the partition strategy. For example, when the query covers a larger amount of bins, several bins can be merged into a single new bin. Laplace noise can be reduced because it is only added once to the new merged bin. When the number of bins covered by a query is relatively small, the curator can either split the large bin into smaller bins, or approximate the query result by estimating proportion of the large bin's frequency. However, splitting the large bin into smaller bins leads to more Laplace noise, while estimating the proportion of the large bin's frequency may introduce estimation error. Therefore, optimizing the partition strategy to obtain a trade-off between splitting and merging bins is a challenge that needs to be addressed. Xu BIB002 provided two partition strategies by minimizing the sum of squared error (SSE) of a set of queries. Both strategies set each attribute as a single bin at an initial state and partition the attribute value to create more bins. The first strategy, NoiseFirst, injects Laplace noise into each bin before partitioning the attribute values. Another strategy, StructureFirst, uses an exponential mechanism to select optimal splitting values of attributes by adopting the SSE as the score function. Qardaji et al. BIB003 partitioned the attribute values in a hierarchical way. They also focus on range queries and allocate ranges into a tree. The root of the tree is the full range of values of an attribute or several attributes. Each node in the tree is associated with the union of the ranges of its children. Several unit-length ranges are defined as leaves. On each branch of the tree, a factor controls the accuracy of the query result. These factors are further studied with a mean squared error (MSE) when answering range queries, and the results are optimized by tuning these factors. Histogram consistency. Even though partitioning is a popular mechanism in histogram releases, this mechanism may bring problems with inconsistency. For example, after adding noise, the summation of two bin's value may be less than one bin. To maintain consistency in histogram publishing, Hay et al. BIB001 defined a constrained inference to adjust the publishing output. Two types of consistency constraints were explored. The first, sorted constraints, requires query results to satisfy a particular sequence. The second, hierarchical constraints, predefines the sequence of a hierarchical interval set. A constrained inference step applies a linear combination method to estimate a set of approximate answers that are close to the noisy answers, which satisfies the consistency constraints. There are some other ways to improve the consistency of the histogram. For example, Lin et al. BIB004 viewed a set of sorted histograms as a Markov chain and proposed an algorithm that applies ordering constraints on the estimates. Lee et al. BIB005 added a post-processing step, formulated as a constrained maximum likelihood estimation problem, before publishing the histogram.