## 3 Implementation and Experiments
### Heuristic vs. Exact Solution  
In Section 3.5, we showed that our greedy heuristic is very efficient and produces good solutions, even if it is (mis)used to solve the classical \(k\)-Anonymity problem. By design, the heuristic always produces solutions where every output row can be matched to some of the specified pattern vectors. However, the number of suppressions performed may be far from being optimal. Hence, by comparing with the exact solutions of the ILP implementation, we try to answer the question of how far the produced solutions are away from the optimum. We evaluate our experiments using the following criteria: \begin{table}
\begin{tabular}{l l l l l l l} \hline \hline \multicolumn{6}{c}{Greedy Heuristic} \\ \hline \(\mathbf{k}\) & \(\mathbf{u}\) & \(\mathbf{r}\) & \(\mathbf{\#}\mathbf{h}\) & \(\mathbf{h_{\text{avg}}}\) & \(\mathbf{h_{\text{max}}}\) \\ \hline  
\hline \hline \end{tabular}
\end{table} 
Table 5: Heuristic _vs._ Mondrian: Results for the Canada dataset. 1. Number \(s\) of suppressions;
2. Usefulness value \(u\);
3. Running time \(r\) in seconds;
4. Number \(\#h\) of output row types;
5. Average size \(h_{\mathrm{avg}}\) of the output row types; and
6. Maximum size \(h_{\mathrm{max}}\) of the output row types. NurseryOur ILP implementation was able to \(k\)-anonymize the Nursery dataset for \(k\in\{2,\ldots,10\), 25, 50, 75, 100\(\}\) within two minutes for each input, that is, we could solve \(k\)-Anonymity with a minimum number of suppressions. In contrast, the ILP formulation could not \(k\)-anonymize the other datasets within 30 min for many values of \(k\). Surprisingly, the results computed by the heuristic were optimal (in terms of the number of suppressed entries) for all tested \(k\), and many results are better in terms of the other quality measures. The reason seems to be that the ILP implementation tends to find, for a fixed number of suppressions, solutions with a high degree of anonymity. For example, the result of the ILP for \(k=6\) is already \(15\)-anonymous, whereas the result of the heuristic is \(9\)-anonymous, yielding more and smaller output row types. Summarizing, the heuristic is at least 25 times faster than the ILP implementation and also produces solutions with a minimum number of suppressions, which have a better quality concerning \(\#h\), \(h_{\mathrm{avg}}\) and \(h_{\mathrm{max}}\) values. See Table 6 for details. CmcConsider the scenario where the user is interested in a \(k\)-anonymized version of the CMC dataset, where each row has at most two suppressed entries. To fulfill these constraints, we specified all possible pattern vectors with at most two \(\star\)-symbols (plus the all-\(\star\)-vector to remove outliers) and applied our greedy heuristic and the ILP implementation for \(k\in\{2,\ldots,10\), 25, 50, 75, 100\(\}\). As expected, the heuristic works much faster than the ILP implementation (at least by a factor of ten). The solution quality depends on the anonymity degree \(k\). The results of the heuristic get closer to the optimum with increasing \(k\). Whereas for \(k=2\), the number of suppressions in the heuristic solution is \(1.4\) times the optimum, for \(k>10\), the heuristic produces results with a minimum number of suppressions. Most other quality measures behave similarly, but the differences are less strong. The usefulness values of the heuristic results are at most as good as those of the ILP results for \(k\leq 7\) and \(k\geq 50\). See Table 7 for details. Adult-2 Consider a user who is interested in the Adult-2 dataset. Her main goal is to analyze correlations between the income of the individuals and the other attributes (to detect discrimination). To get useful data, she specifies four constraints for an anonymized record. 1. Each record should contain at most two suppressed entries. 2. The attributes \"education\" and \"salary class\" should not be suppressed, because she assumes a strong relation between them. 3.