{'fraction_non_alphanumeric': 0.03222335931144874, 'fraction_numerical': 0.01165079115169645, 'mean_word_length': 4.978039215686275, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Chasing Accuracy and Privacy, and Catching Both: A Literature Survey on Differentially Private Histogram Publication

Histograms and synthetic data are of key importance in data analysis. However, researchers have shown that even aggregated data such as histograms, containing no obvious sensitive attributes, can result in privacy leakage. To enable data analysis, a strong notion of privacy is required to avoid risking unintended privacy violations. Such a strong notion of privacy is differential privacy, a statistical notion of privacy that makes privacy leakage quantifiable. The caveat regarding differential privacy is that while it has strong guarantees for privacy, privacy comes at a cost of accuracy. Despite this trade off being a central and important issue in the adoption of differential privacy, there exists a gap in the literature for understanding the trade off and addressing it appropriately. Through a systematic literature review (SLR), we investigate the state-of-the-art within accuracy improving differentially private algorithms for histogram and synthetic data publishing. Our contribution is two-fold: 1) we provide an understanding of the problem by crystallizing the categories of accuracy improving techniques, the core problems they solve, as well as to investigate how composable the techniques are, and 2) we pave the way for future work. In order to provide an understanding, we position and visualize the ideas in relation to each other and external work, and deconstruct each algorithm to examine the building blocks separately with the aim of pinpointing which dimension of noise reduction each technique is targeting. Hence, this systematization of knowledge (SoK) provides an understanding of in which dimensions and how accuracy improvement can be pursued without sacrificing privacy.


I. INTRODUCTION
Being able to draw analytical insights from data sets about individuals is a powerful tool, both in business, and in research. However, to enable data collection, and consequently data analysis, the individuals' privacy must not be violated. Some strategies [1]- [3] for privacy-preserving data analysis focus on sanitizing data, but such approaches requires identifying sensitive attributes and also does not consider auxiliary information. As pointed out by Narayanan and Shmatikov [4], personally identifiable information has no technical meaning, and thus cannot be removed from data sets in a safe way. Furthermore, Dwork [5] proves that for essentially any non-trivial algorithm, there exists auxiliary information that can enable Both the authors contributed substantially, and share first authorship. The names are ordered alphabetically. a privacy breach that would not have been possible without the knowledge learned from the data analysis. Consequently, a strong notion of privacy is needed to avoid any potential privacy violations, while still enabling data analysis.
Such a strong notion of privacy is differential privacy [6] (Section II), which currently is the de-facto standard for private data analysis [7], [8]. Differential privacy is a privacy model that provide meaningful privacy guarantees to individuals in the data sets. Essentially, differential privacy allows an analyst to learn statistical correlations, without inferring information about any one individual.
Differential privacy has spurred a flood of research in devising differentially private algorithms for various data analysis tasks. In this work, we focus specifically on differentially private algorithms for histogram, and synthetic data publication. Histograms and synthetic data are particularly interesting because they provide approximation of the underlying data distribution and synthesis of original data respectively.
There are many algorithms for histogram and synthetic data publishing that achieves accuracy improvement for a fixed privacy level, . Most often than not, accuracy improvement is achieved through pre-processing the data set, post-processing the query results, using query optimization techniques, or algorithmic tricks that exploits the properties of the data, as illustrated in Figure 1. There exists only a few works concerning understanding the basic construct of privacy-accuracy trade off in differentially private computations. This gap in understanding the constructs of privacy-accuracy trade off limits the space of differentially private accuracy improvement techniques that tackle the core problems in acheiving accuracy.
Previous literature surveys [9]- [11] either focus only on a single data analysis for example either histogram or synthetic data, or focus on an arbitrarily selected set of papers. Furthermore, previous work do not scrutinize and analyze the components of each studied algorithms, but instead their categorization of algorithms is based on each algorithm as a whole. Consequently, to bridge the knowledge gap, we conduct a systematic literature review (Section III) on accuracy improvement techniques for differentially private histogram and synthetic data publication. Thus our aim is: to summarize the state-of-the-art (Section IV), identify trends in the literature, and to analyze the constructs of differentially private accuracy improvement strategies, in order to pave the way for future research.
Our contribution is a systematically structured, qualitative analysis (Section V) of accuracy improving differentially private histogram or synthetic data publishing algorithms. More concretely, we provide: 1) A summary of the distinct parameters of each algorithm (Section IV-A), 2) An overview of how the different algorithms are related internally in our survey, as well as to algorithms outside (Section V-A, V-B 3) We pinpoint different dimensions of noise reduction strategies to improve accuracy (Section V-C, and 4) An overview of how the different techniques can be composed to build new algorithms (Section V-D.

II. DIFFERENTIAL PRIVACY
Differential privacy [6] is a statistical definition that enables privacy loss to be quantified and bounded. In -differential privacy, privacy loss is bounded by the parameter . The formal definition of -differential privacy is given in Definition 1.
Definition 1 ( -Differential Privacy [5]): A randomized algorithm M gives -differential privacy if for all data sets D 1 and D 2 differing on at most one element, and all S ⊆ A relaxed version of differential privacy is ( , δ)-differential privacy, Definition 2. ( , δ)-differential privacy allows the mechanism to sometimes, in extremely unlikely cases, release an answer with much better or worse accuracy. In ( , δ)differential privacy privacy loss is bounded by with probability at least 1-δ. That is, the probability of gaining significant information about one individual, even when possessing all other information in the data set, is at most δ. Note that -differential privacy is a special case of ( , δ)-differential privacy with δ = 0. Definition 2 (( , δ)-Differential Privacy [12]): A randomized algorithm M is ( , δ)-differentially private if for all data sets D 1 and D 2 differing on at most one element, and all S ⊆ Range(M), Pr[M(D 1 ) ∈ S] ≤ e × Pr[M(D 2 ) ∈ S] + δ When δ = 0, the algorithm is -differentially private.
The semantic interpretation of the privacy guarantee defined in Definition 1, rests on the definition of what it means for a pair of data sets to be differ by one element. In the literature, the following two variations of neighbors are considered when defining -differential privacy guarantee.
Definition 3 (Unbounded differential privacy): D 1 and D 2 are neighbors iff D 1 can be attained by adding or removing a single record in D 2 .
Definition 4 (Bounded differential privacy): D 1 and D 2 are neighbors iff D 1 can be attained by changing a single record in D 2 .
Distinguishing between the definition of neighboring data sets is important, because it affects the global sensitivity of a function. The sizes of the neighboring data sets are fixed in the bounded differential privacy definition whereas, there is no size restriction in the unbounded case.
In the case of graph data sets, a pair of graphs differ by their number of edges, or number of nodes. Therefore, there exists two variant definitions in literature [13] that formalize what it means for a pair of graphs to be neighbors. Nevetheless, these graph neighborhood definitions are defined only in the context of unbounded differential privacy.
Definition 5 (Node differential privacy [13]): Definition 6 (Edge differential privacy [13]): To statisfy differential privacy, a randomized algorithm injects noise to the query answers to obfuscate the impact caused by the presence or absence of an individual in the data set. The difference between the answers to a query when an inividual is in the data set or not in the data set, is the difference the noise will need to obfuscate. This difference is defined as L 1 sensitivity of a function f or query on a data set.
Definition 7 (L 1 Sensitivity [6]): The L 1 sensitivity of a function f : D n → R d is the smallest number S(f ) such that for all x, x ∈ D n which differ in a single entry, Since differential privacy is a property of the algorithm, as opposed to data, there exists many implementations of differentially private algorithms. Thus, we will not summarize all algorithms, but instead introduce two early algorithms that are common building blocks, namely: the Laplace mechanism [6] and the Exponential mechanism [14].
Definition 8 (Laplace mechanism [15]): For a query f on data set x, mechanism M responds with: f (x)+(Lap(∆f / )) Definition 9 (Exponential mechanism (EM) [14]): For any function q : (D n × R) → R, and base measure µ over R, we define ε q (d) := Choose r with probability proportional to e ( q(d,r)) × µ(r) To acheive trival accuracy improvement the parameter can be tweaked. However, tweaking to achieve accuracy increases the privacy loss. In certain settings, grows too fast to guarantee a meaningful privacy protection. To cater to different applications, in particular for data streaming, different privacy levels have been introduced. They are, User level privacy All data connected to one individual shares a joint privacy budget. Implicitly used in the original definition of differential privacy. Event level privacy [16] Every data point is considered independent and thus has its own budget w -event level privacy [17] A set of w events are considered dependent and share a joint privacy budget. If w = 1, w -event level privacy and event level privacy are the same.

III. METHOD
Our systematic literature review (SLR) [18] consists of the following stages shown in Figure 2.

A. Query Construction
We used the semantic search engine Microsoft Academic [19], [20]. As opposed to a syntactic search engine, Microsoft Academic connects papers to entities that represents for example topics, authors and conferences. Consequently, when using Microsoft Academic, there is no need to insert synonyms to words because of the semantic search engine. Thus, in our SLR we used two queries, one for each data type.

B. Exclusion Criteria
The list of exclusion criteria (Table I), was manually checked against the abstract of each paper. When a paper matches any one of the criteria, it is excluded, otherwise the paper is included.
Due to space limitations, the full list of excluded papers can be found online 1 . 1 https://github.com/jennshan/Sok Chasing Accuracy and Privacy Exclude if the papers is... 1) not concerning histograms or synthetic data 2) not concerning pre-processing/post-processing/algorithmic tricks to solely improve accuracy 3) a trivial improvement of accuracy through relaxations of differential privacy or adversary model 4) concerning local sensitivity 5) outputting a machine learning model 6) pure theory, without empirical results 7) a patent 8) not releasing a histogram/synthetic data 9) a PhD thesis 10) not in English Table I: Exclusion criteria

C. Qualitative Analysis and Categorization
The analysis was carried out by two people, each of which deep-read a disjoint half of the papers to be the 'expert' for. Then, all papers were tagged visually to be able to make connections between papers. In parallel, each paper was discussed and disseminated.
The method used for identifying different categories was a hybrid combination of top-down and bottom-up. That is, categories were designed both prior to the analysis (top-down) as well as identified from reading the papers (bottom-up). Then, the two views were merged to capture the different flavor of topics.

IV. OVERVIEW OF PAPERS
All included papers and their corresponding algorithms are listed in Table II. The techniques used by different algorithms are then categorized in Table III.

A. Categorization of approaches
Given that our two queries were designed to capture either synthetic data or histogram papers, we examine how similar the algorithms from the queries are, and manually represent them as partly overlapping sets, as visualized in Figure 3. We distinguish between the two data types by their different goals: for histograms, the goal is to release one optimal histogram for a given set of queries, whereas for synthetic data the goal is to release a database that is optimized for a set of queries. Some algorithms use similar approaches to the algorithms from the other query; and therefore we put them in the intersection.
In Figure IV, we present objective details of the algorithms in each paper, to show the different settings they operate in, which allows for further understanding of which papers are comparable.

V. ANALYSIS
We provide an analysis where we view the papers from different perspectives: how they relate to each other (Section V-A), how they relate to other work (Section V-B), which dimension of accuracy improvement are covered by different techniques (Section V-C), and the composability of these techniques (Section V-D).

A. Internal positioning
To understand the relationships between the papers we have analyzed, we provide a connection between them in Figure 4. We show connections between papers that either build on each other's ideas, or when authors compare their algorithms through experiments. Then, we focus on analyzing the outliers; namely the papers with many or no connections. HRMS10 [22] provides post-processing through consistency checks, which means it is not only comparable to other algorithms, but also composable with many algorithms, thus making it popular. LWK15 [36] is similar to HRMS10, but LWK15   XZXYYW13 [27] introduce differentially private histogram partitioning, using a two-phased approach combining the Laplace mechanism and the exponential mechanism, which is then continued by others. ACC12 [29] continues the the line of research from XZXYYW13, but with an improved clustering technique. ZCXMX14 [48] build upon both XZXYYW13 and ACC12, but extend the idea by focusing on the improving the trade off between the two phases. LCMM19 [35] also continue the line of thought by XZXYYW13 and ACC12, but focus on improving the accuracy for large, sparse data sets by devising an algorithm whose sensitivity is independent of the data set size. DWHL11 [25] is quite different from the other papers as they work with data cubes, and propose an approximate algorithm for a NP-hard selection problem. XXFGL14 [31] also work on data cubes, but their solution to the problem focuses on partitioning with equi-width histograms or kd-trees, which is completely different from DWHL11. Another data type that stands out is the spatial data used by GKR18 [45], and as there were no other papers focusing on such data, there are no internal connections. KMHM17 [46] is a bit of a special case, since Pythia essentially chooses the best algorithm for a given data set, and does not provide a new way of releasing data. Comparably, PG14 [37] is alone in using dirichlet prior perturbation, and it also stands out by compressing data using feature hashing. Two papers use local differential privacy, but WHWDXY16 [40] design a sophisticated way of weighting the privacy budget that is very different from the techniques used by NYHXZW19 that also uses local differential privacy.
Lastly, LMG14 [34] is mainly concerned with redefining the neighboring relationship to enable relational databases to be synthetically generated, which is not covered by any other paper in the survey. However, this way of redefining neighboring data sets reminiscent of the introduction of node and edge privacy for graphs.

B. External positioning
In Figure 5 we visualize how the surveyed papers connect to other papers. Here, we have the chance to include more theoretical work, as those were purposely excluded in our SLR.
The most frequent common denominator from outside work is the matrix mechanism from LHRMM10 [81]. Several papers in our survey use the matrix mechanism as part of their own algorithm. Furthermore, the data-aware DAWA algorithm from LHMW14 [82] is often used as a comparison during the experiments. GS by KG13 [68] is also a popular algorithm to use in comparisons, both for papers using event level privacy and others. Papers dealing with dynamic data also compare to BA by KPXP14 [17].
The idea of v-optimal histograms was introduced by JKMPSS98 [58], and was first combined with differential privacy by XZXYYW13 [27]. The papers that are connected to JKMPSS98 are due to their connection to XZXYYW13. ACC12 [29] EFPA extends the SPA algorithm from RN10 [53]. The line of research considering Fourier transforms was originally introduced by BCDKMT07 [83] with the FPA algorithm. PG14 [37] uses the idea of dirichlet prior, as introduced by MKAGV08 [49]. Some papers also use, or compare to, MWEM from HLM12 [60], which builds on HR10 [55].
The few papers that cover local differential privacy, WH-WDXY16 and NYHXZW19, either compare to, or are inspired by DJW13 [50], respectively.

C. Dimensions of Accuracy Improvement Techniques
Three different groups of optimization goals are observed in the papers that we analyzed in this SLR. The goals are; i) Figure 5: Positioning the papers to outside work [7], [17], [49]- [81], external papers in the middle with size relative to their popularity. Papers without external connections not pictured.
to reduce the accumulated noise, ii) to reduce sensitivity and iii) to reduce curse of high dimensionality. Figure V shows the accuracy improving techniques grouped by their optimization goals.

Accumulated noise reduction
As mentioned in Section II the Laplace mechanism, which is a standard algorithm for releasing numerical values adds noise of scale ∆f / to a query answer.
In differentially private histogram publishing using the Laplace mechanism, noise of scale 1/ is added to each bin in the histogram. When the number of histogram bins is large (finer grained bins), the noise error is large, especially when the value of is small. However, if the bin ranges are large (coarse grained bins), but the bins are not uniformly populated, the result will suffer from approximation error. Intuitively, the accuracy is improved by finding a trade off between these two errors.
Algorithms SF [27], P-HP [29], mIHP [35] and Outlier-HistoPub [44] employs differentially private clustering to find the sub-optimal histogram bin partitioning. In Outlier-HistoPub an additional pre-processing step is used for smoothing the data distribution before applying differentially private clustering.
In the differentially private clustering, exponential mechanism is used to identify clusters. The quality of the clusters depends on the proportion of privacy budget, , allotted to the exponential mechanism. When a large number of clusters are considered, which is the case in multidimensional data set, the quality of clusters becomes imprecise because of small privacy budget available for iterating the exponential mechanism. The clustering technique used in NF [27], AHP [48], DPCube [31] and DPCocGen [23] instead operates on fine grained noisy histograms to find good partitioning strategy. Once the partitioning for the given data is obtained, a new noisy optimal histogram is released using the Laplace mechanism. Interestingly, Li et al. [35] considers another error component besides the noise error and the approximation error. The third error component captures the effect of exponential mechanism during the partitioning step. Their algorithm mIHP [35] finds a trade off between these three errors.
Instead of finding an optimal histogram for a given data set, another opportunity to improve the accuracy of a histogram is by adding varying amount of noise to different bins. Wang et al. in their BPM algorithm split the histogram bins into two disjoint sets; heavy hitters, and less interesting bins. The privacy budget is carefully split between these bins such that the heavy hitters enjoys less noise. However, this optimization is proposed for bitmap strings under local differential privacy.
Now, consider another case where the purpose of the releasing a differentially private histogram is to answer a random workload of allowable queries. When the workload contains irregular and large ranges, and if the histogram is optimized for the given data set as we saw above, the answer to the workload involves counts of many small range bins. Consequently, the noise error of the final answer is the sum of noise of every unit-length counts (sequential composition of differential privacy). Intuitively, if the answer to the workload can be constructed by finding a linear combination of few number of noisy counts, then accuracy of the final answer will be significantly improved.
Algorithms Boost [22], DPCube [31], PrivTree [42] and Tru, Opt [26] employ a strategy where the domain ranges are hierarchically structured, typically in a tree structure. The leaves are unit-length intervals, and the root amounts for the entire domain range. Each internal node contains the sum of the counts of its children. The intuition is, to find the fewest amount of internal nodes such that the union of these ranges equals the desired range in the workload. To further boost the accuracy, in Boost the authors propose a strategy that imposes constraints in the output space of possible answers, which are used in the post-processing step to identify more accurate answers in the output space. Following the result of Boost, DPCube uses the post-processing step to improve accuracy. The fanout of the tree is fixed in most of the above mentioned algorithms, except in Opt, where the fanout of the tree is adaptively adjusted.
In PrivTree, Zhang et al. demonstrates that fixed amount of noise is sufficient to ensure differential privacy as opposed to the noise calibrated to the height of the tree. This improves the accuracy of the noisy counts.
Algorithm CiTM [34] uses the idea of hierarchical decomposition (query tree) for relational databases with complex schema. To account for elaborately correlated counting queries, Lu et al. proposes a reverisble transformation called denormalization on the relations. Furthermore, they extends the differential privacy guarantee (Definition 1) to include privacy protection for tuples that are correlated.
In Privelet [24], the domain values are transformed into wavelet coefficients. Each wavelet coefficient is a linear combination of ranges in the histogram. Answers to any range query can thus be reconstructed by consulting a few wavelet coefficients.Ács et al. [29] uses discrete Fourier transformation to compress the domain space. Top k Fourier coefficients are identified in order to reduce the noise error. Algorithm EFPA [29], however is an extension of SPA [53] algorithm. In EFPA, an improved version of exponential mechanism is used to identify the value k.
The RCF algorithm proposed by Nie et al. [21] linearly combines nosiy estimates to answer a given query under local differential privacy. The linear combination strategy is, however, used as a post-processing step in their application settings.
When a dynamic data set is used to answer a workload, the optimization techniques listed above are not directly applicable, since batch processing is not desirable for analysis of dynamic data. Furthermore, knowledge about the target queries cannot be predicted. To reduce the noise that accumulates under sequential composition, we observed two approaches in the literature that concerns dynamic data. One approach is workload-aware optimization, and another approach is to avoid releasing almost the same histogram multiple times. To preserve the dependency constraint among the bins in the histogram, PrivSH [45] uses the more informative query from the workload to update the differentially private model that approximates the underlying data distribution. Upon completion of the model, synthetic data is generated through sampling. Algorithms RG [39], DSAT, DSFT [28] and GGA [33] on the other hand, publish a new histogram only if there is a significant change in the data set. These three algorithms use a threshold value to measure the change, in DSAT however, the threshold value is adaptively chosen under differential privacy.

Sensitivity Reduction
As mentioned in Section II, the choice of neighborhood affects the global sensitivity of a function. For a function under unbounded differential privacy, the L 1 sensitivity of a function considers all pairs of neighboring data sets of varying sizes. In the graph domain, for most of the functions on a graph data set, function sensitivity under node differential privacy becomes unbounded. This is because, removal of a node and its edges may, in worst case, results in removal of all the edges in the input graph. Since the effect that adding/removing a node has on the function's output depends on the size n of the graph, which is unbounded, the sensitivity is unbounded as well.
Differential private algorithms in this group perform a preprocessing step to bound the size of the graph, thus bounding the function sensitivity, which in turn will results in reduction of noise required to satisfy node differential privacy. (θ, Ω)-Histogram [43] and T λ [38] apply graph projection for bounding the size of the graph. (θ, Ω)-Histogram and T λ are optimized for degree distribution and triangle count queries respectively.
Additionally, (θ, Ω)-Histogram includes differentially private clustering and post-processing techniques to further boost the accuracy of the degree distribution histogram. In the postprocessing step Day et al. uses either linear regression, or power law distribution or uniform distribution in order to infer and reallocate counts of degrees that were originally truncated by the projection process.
Further, Ding et al. [38] and Day et al. [43] suggests to release a cumulative histogram for specific degrees. The sensitivity of the cumulative histogram is lesser than the general histogram thus the resulting histogram is much more accurate.
Curse of dimensionality reduction When the data set is high-dimensional with large domain sizes, reducing the noise by means of clustering the data set as histogram is not computationally feasible, and it is also difficult to find an optimal histogram. Because, as most of the counts will be zero in a sparsely populated data set, even after clustering the noise incurred by zero count, bins are ridiculously large, which makes the answer utterly useless. The problem is further aggravated when the goal is to release the private data to answer a workload of any set of queries. Thus, to achieve multiple private releases, yet preserving the usefulness of the answers, the underlying distribution of the data set is released. The release, optionally can be populated with synthetic values, and the idea is that the release will answer any further predicate queries. When the target queries or the underlying data distribution is not known in advance, the techniques listed in the above section does not improve the accuracy of the estimated synthetic data. However, if the underlying distribution is inferred from a set of low-dimensional marginal distributions, then the impact of noise on the accuracy is contained to a smaller set of attributes.
Accordingly, the techniques PrivBayes [41], DPcopula [30], Pmost, Bmax [25], DPPro [32], and PeGS, PeGS.rs [37] in this group decompose the high-dimensional domain space into a subset of low-dimensional domain spaces. The low-dimensional marginal distributions are then used to infer the joint distribution that approximates the underlying data distribution.

D. Composability of Approaches
From the dimensions identified in the previous section, we take our analysis further by investigating how subset of techniques may be composed. We also connect the papers with the place 2 their algorithm operates on in Table VI.
Sensitivity reduction) As sensitivity is a property of the query, there is a clear limit to how much sensitivity can be reduced. In our SLR we identified, changes to sensitivity is achieved by breaking down a query. Histogram query is broken down into two separate queries: usually a Laplace counting query and a clustering technique based on the exponential mechanism, as in the case with [27] and consecutive work. 2 Places refers to different points in the workflow of a typical differentially private analysis, see Figure 1 Optimization   [25] WGXLY17 [26] XZXYYW13 [27] LXJL15 [84] ACC12 [29] LXJ14 [30] XXFGL14 [31] XRZQR17 [32] GM18 [33] LMG14 [34] LCMM19 [35] LWK15 [36] PG14 [37] DZBJ18 [38] CSJ15 [39] ZCPSX14 [41] ZXX16 [42] DLL16 [43] HSLMZD16 [44] GKR18 [45] KMHM17 [46] DM17 [47] ZCXMX14 [48] Table VI: Mapping the papers to each place where: A) Altering the query, B) Post-processing, C) Change in mechanism, D) Pre-processing Another approach is through pre-processing the data set by means of thresholding or projection in order to bound the maximum difference between the neighboring data sets. This pre-processing step is showed to compose with algorithmic tricks and post-processing strategies. For example, in PrivTree [42], (θ, Ω)-Histogram [43] and CiTM [34] thresholding is combined with hierarchical decomposition/clustering and postprocessing.
Data dimensionality) Dimensionality can be reduced to such a point that there still is sufficient important information to carry out an analysis on. It still must be possible to extract useful information from the data set after dimensionality reduction. However, dimensionality reduction will be a source of extra noise as well, provided it is not lossless, so it is not a clear cut case when dimensionality reduction stops being a beneficial method.
In the SLR, we identify different forms of projections and transformations as effective dimensionality reduction approaches. Each paper only uses one dimensionality reduction technique, and we have not yet seen composition of these techniques. Dimensionality can be addressed in place C and D, by using techniques in the algorithm or as part of the preprocessing step.
Dimensionality reduction can also be achieved through a divide-and-conquer approach. We see this in, for example, Li et al. [30] considers composability in DPCopula, which is not intended for small domains. They propose that it is possible to pre-partition small domains using DPCube [31], EFPA [29], PSD [59], and then compose the output with DPCopula on large domains.
Accumulated noise) Accumulated noise can be tackled through a diverse arsenal of techniques. In this dimension, there is no clear limit to how many techniques can be composed; but it rather seems to depend on the aspects of the data, which ones can be successfully employed. Noise accumulation is tackled in places B, C and D, post-processing, changes in the mechanism and pre-processing respectively.
For example, the exponential mechanism relies on a utility function that with high probability releases a value statistically close to the real answer. Thus, the exponential mechanism can be used in many settings, but the success is entirely decided by which utility function is used. Consequently, the exponential mechanism is highly dependent on the nature of the data domain, as opposed to the real data, as this decides the metric used in the utility function. Coming up with new or adopting existing metrics can therefore be an interesting research direction to reduce accumulated noise.
Another aspect of data that can be used to avoid accumulated noise is to exploit consistency constraints. Patterns in the data can be enhanced in the pre-processing step and then validate the consistency constraints in the post-processing step. One such example is SORTaki [47], where the bin counts are ordered before the histogram is constructed, which then enables consistency checks.

VI. DISCUSSION
One limitation of our method is that the SLR is limited to papers with empirical results, since empirical measurement of accuracy provide a better understanding of the error bounds. However, in our analysis (Section V) of the papers, we studied related theoretical aspects of accuracy improvements and present the results in Figure 5.

A. Incomparable papers
A list of papers are excluded in the results presented in the Section V. This is because, certain properties of their algorithms make them incomparable with other algorithms. In Table VII, we list the papers along with the reasons for not  including them in the results. Yan et al. [85]: the DP-FC algorithm does not consider the structure of the histogram a sensitive attribute, and thus achieves a trivial accuracy improvement over other algorithms. Liu and Li [86]: the APG algorithm does not perform differentially private clustering, and therefore achieves better accuracy by relaxing the privacy guarantees compared to AHP, IHP and GS. Qian et al. [87]: SC algorithm uses the ordering of the bins in order to calculate the cluster centers, but does not perturb the values before doing so, and thus the order is not protected, making their guarantees incomparable. Li and Li [88]: the ASDP-HPA algorithm does not describe the details of how their use of Autoregressive Integrated Moving Average Model (ARIMA) is made private, and thus we cannot distinguish if the entire algorithm is differentially private. Furthermore, the details of how they pre-process their data set is not divulged, and it can thus not be determined if the pre-processing violates differential privacy or not.
Hadian et al. [89]: the algorithm is incomplete, since it only covers the histogram partitioning, and does not involve the addition of noise to bins. Furthermore, it is not clear whether they draw noise twice using the same budget, or if they reuse the same noise for their thresholds. As the privacy guarantee cannot be unambiguously deduced, we do not include their paper in our comparison. Chen et al. [90]: GBLUE generates a k-range tree based on the private data, where k is the fanout of the tree. Since private data is used to decide on whether a node is further spilt or not, it does not provide the same privacy guarantees as the other studied algorithms. Li et al. [84]: In their algorithm, groups are formed on the condition that the merged bins guarantee k-indistinguishability. Since this merge condition is based on the property of the data it does not guarantee differential privacy on the same level as the other papers, so we deem it incomparable. Table VII: Incomparable papers along with the reasons for excluding them in the analysis Further, in the analysis regarding dimensions of accuracy improvement techniques presented in Section V, some algorithms such as Boost [22], ADMM [36], SORTaki [47] and Pythia [46] are excluded. The rationale behind the exclusion is, these algorithms are not self contained, but nevertheless improves accuracy of the differentially private answers when combined with other analyzed algorithms.
Efforts such as Pythia [46] and DPBench [91] that provide practitioners, a way to empirically assess the privacy-accuracy trade off related to their data sets are commendable. However, to effectively use the tool one needs to have some background knowledge of the right combination of parameters to tune. In our analysis of the algorithms, we mapped out the accuracy improvement techniques grouped by optimization goals and corresponding query size. This knowledge will allow practitioners and researchers alike to think about other places to explore for accuracy improvement, rather than finding the algorithms that are based only on their data. VII. CONCLUSIONS Motivated by scarcity of works that aims to structure knowledge concerning accuracy improvement in differentially pri-vate computations; we conducted a systematic literature review (SLR) on accuracy improvement techniques for histogram and synthetic data publication under differential privacy.
We present three results from our analysis that answers our research objective: To synthesis the understanding of the underlying foundations of the privacy-accuracy trade off in differentially private computations. One, internal/external positioning of the studied algorithms. Two, different dimensions of accuracy improvement: accumulated noise reduction, sensitivity reduction and data dimensionality reduction. Third, we provide an overview of composable algorithms according to their dimensions, sort-out by the places, in which they operate. Our findings pave the way for future research by allowing others to integrate new solutions according to the noise reduction dimensions.
From our overview of composability, we see that most efforts are focused on making changes in the mechanism, and on post-processing. We believe from our comprehensible categorization of the different approaches, that, it is possible to take ideas from other disciplines and plug them in as new techniques, which opens the door for many possible research directions. We observe that, altering the query in one way or another, is not popular, and we believe further investigation is required to understand which techniques can be adopted in this place.