# A New Approach to Privacy-Preserving Multiple Independent Data Publishing
## 5 Experimental Analysis
### Data Utility
#### 5.3.2 Aggregate Query Answering Error  
In this experimental analysis, the accuracy of aggregate query answering [47] was also evaluated as a measure of data utility. It is possible to compute aggregate query operators such as \"COUNT\", \"MAX\", \"AVERAGE\" and so on. In the experiment, only the \"COUNT\" operator was evaluated, for queries whose predicates involved the sensitive values. The query is considered in the following form:  
SELECT COUNT(*) FROM Table  
\[\text{WHERE }v_{i_{1}}\in V_{i_{1}}\text{AND}\ldots v_{i_{dim}}\in V_{i_{dim}} \text{AND}\ s\in V_{s}\]  
where \(v_{i_{j}}(1\leq j\leq dim)\) is the quasi-identifier value for attribute \(AT_{i_{j}},V_{i_{j}}\subseteq D_{i_{j}}\) and \(D_{i_{j}}\) is the domain for attribute \(AT_{i_{j}},s\) is the sensitive attribute value, \(V_{s}\subseteq D_{s}\) and \(D_{s}\) is the domain for the sensitive attribute S. A query predicate is characterized by predicate dimension \(dim\) and query selectivity \(sel\), \(dim\) indicating the number of quasi-identifiers in the predicate and \(sel\) indicating the number of values in each \(V_{i_{j}},(1\leq j\leq dim)\). The size of \(V_{i_{j}},(1\leq j\leq dim)\) was randomly chosen from \(0,1,\ldots,sel*|D_{i_{j}}|\). Each query was executed on seven tables: the original and those generated by the Merging, \(\epsilon-DP\), Hybrid, Probabilistic, Composition and Mondrian methods. Count is indicated for the original and anonymized tables, the original count denoted by \(org_{count}\) and the anonymized count by \(anz_{count}\), where \(anz_{count}\) is Merging, \(\epsilon-DP\), Hybrid, Probabilistic, Composition and Mondrian respectively. To measure the average relative error in the anonymized dataset, we compute all queries as described in [47]:  
\[Relative\ error=\frac{|anz_{count}-org_{count}|}{org_{count}}\times 100\%\]  
In Figure 6, relative query error is plotted on the Y-axis based on the quasi-identifier selection. In the experiment, we selected one, two, three, four or five attributes as quasi-identifiers and calculated the relative query error on the anonymized tables generated by Merging, \(\epsilon-DP\)[37], Hybrid [2], Probabilistic [23], Composition [24] and Mondrian [44] methods. For example, suppose we want to calculate the relative query error by Merging for Table 6, and the corresponding query is  
SELECT COUNT(*) FROM Table 3  
WHERE (sex='F') AND (Disease='Fever')  
Figure 5: Data loss in the published dataset.  
From the query answer, there is only one female person suffering from Fever. However, from the original table, i.e., Table 1, the query answer will be two persons. Using a relative error formula, it could be shown that Merging has a 50% relative query error for one attribute selection. For the experiment, all possible combinations of the query were generated and executed across anonymization tables for the 4.5 K Occupation dataset and the average relative query error was calculated, with \(k\) set to 6 for the Mondrian, Hybrid, \(\epsilon-DP\), Probabilistic, Composition methods and \(l\) set to 6 for Merging. The relative query error was calculated and is shown in Figure 6, where the value on the _Y-axis_ denotes relative error percentage and those on _X-axis_ stand for different quasi-identifier selections. While the Merging method creates fake tuples in the anonymization, it can be seen from the experimental result that Merging still has small relative error compared with all other methods. For the generalization of attribute values, one needs to consider all possible combinations for a particular query answer. Therefore, the competing methods demonstrate the higher relative query error for the anonymized datasets.