## 3 Implementation and Experiments
### Heuristic vs. Mondrian  
In this subsection, we evaluate our experiments. Observe that the Mondrian algorithm does not suppress entries, but replaces them with some more general one. Hence, the number of suppressions as quality criteria is not suitable in the comparison; instead, we use the usefulness as defined in Section 3.3. Overall, we use the following criteria:  
1. Usefulness value \(u\);
2. Running time \(r\) in seconds;
3. Number \(\#h\) of output row types;
4. Average size \(h_{\mathrm{avg}}\) of the output row types; and
5. Maximum size \(h_{\mathrm{max}}\) of the output row types. Except for \(\#h\), lower values indicate better solutions. For each dataset, we computed \(k\)-anonymous datasets with our greedy heuristic and Mondrian for \(k\in\{\)2, 3, \(\ldots\), 10, 25, 50, 75, 100\(\}\). In the presented tables comparing the results of the Greedy Heuristic and Mondrian, we highlight the best obtained values with light gray background. General ObservationsThe running time behavior of the tested algorithms is somewhat unexpected. Whereas Mondrian gets faster with increasing \(k\), our greedy heuristic gets faster with decreasing \(k\). The reason why the greedy heuristic is faster for small values of \(k\) is that usually the cheap pattern vectors are used, and hence, the number of remaining input rows decreases soon. On the contrary, when \(k\) is large, the cheap pattern vectors cannot be used, and hence, the greedy heuristic tests many pattern vectors before it actually starts with removing rows from the input matrix. Thus, for larger values of \(k\), the greedy heuristic comes closer to its worst-case running time of \(O(pnm)\) with \(p=2^{m}\). AdultOur greedy heuristic could anonymize the Adult dataset in less than three minutes for all tested values of \(k\). For \(k=3\) and \(k=4\), [PERSON] took more than half an hour to anonymize the dataset. However, in contrast to all other values of \(k\), Mondrian was slightly faster for \(k=75\) and \(k=100\). Except for \(h_{\mathrm{max}}\) with \(k\geq 25\), all quality measures indicate that our heuristic produces the better solution. Adult-2 The solutions for Adult-2 behave similarly to those for Adult. Our greedy heuristic with a maximum running time of five seconds is significantly faster than Mondrian with a maximum running time of 20 min (at least 10 times faster for all tested \(k\)). However, the usefulness is quite similar for both algorithms. Mondrian beats the heuristic by less than 1% for \(k=50\); the heuristic is slightly better for each other tested \(k\). See Table 2 for details. NurseryFor the Nursery dataset, the heuristic is at least eight times faster than Mondrian. Concerning solution quality, this dataset is the most ambiguous one. Except for \(k=5\), Mondrian produces better solutions in terms of usefulness, whereas our heuristic performs better in terms of maximum and average output row type size. For the number of output row types, there is no clear winner. See Table 3 for details. CmcFor the CMC dataset, both algorithms were very fast in computing \(k\)-anonymous datasets for every tested \(k\). Mondrian took at most 10 s, and our greedy heuristic took at most 1.2 s and was always faster than Mondrian. As for the solution quality, the heuristic can compete with Mondrian. The usefulness of the heuristic results is always slightly better. The Mondrian results have always at least 20% less output row types, and the average output row type size of the heuristic results is always smaller. Only for \(k=5,6,7\), and \(8\), the Mondrian results have a lower maximum size of the output row types. See Table 4 for details.