## 5 Experiment Evaluations
### Results and Discussion  
Figure 7 shows the execution times for varying the number of query results. During the experiments, various numbers of query results were obtained by controlling the values of \(min_{height}\) and \(max_{height}\). The key observations, based on Figure 7, can be summarized as follows: the proposed method (_Est_kAnonymity_ that is based on local anonymization in a distributed environment) significantly outperforms the original _k_-anonymity algorithm (_kAnonymity_ that is based on global anonymization in a distributed environment) in terms of the execution time. As the number of results increases, the performance gap between _Est_kAnonymity_ and _kAnonymity_ increases. Figure 7 also shows whether the generalization level of each quasi-identifier attribute for _k_-anonymity is correctly estimated (marked with 'C' in the figure), or under- or overestimated (marked with a 'U' or 'O', respectively, in the figure) by the estimation method described in Section 4.1. As can be seen in Figure 7, the underestimation causes a slight increase in the execution time because the anonymization is applied on the actual query result dataset by the master node. Figure 8 plots the loss metric (LM) [57] for varying the number of query results. Note that LM measures the amount of information that is lost due to a generalization of the quasi-identifier attributes, ranging from zero to one (a lower value is better). The proposed method, \(Est\_kAnonymity\), shows a very similar pattern with \(kAnonymity\) in terms of the LM. As can be seen in Figure 8a, the LM slightly increases with the proposed approach. In particular, the increases are observed when the generalization level is overestimated. This is because the overestimation causes the values of the quasi-identifier attributes to be more generalized than needed, which results in the increased LM. However, the underestimation does not lead to an increase in the LM, the reason for which is that, in the case of an underestimation, the values of the quasi-identifier attributes are less generalized, and thus the master node applies further anonymization on the actual aggregated results until \(k\)-anonymity is satisfied, which corresponds to Phase III in Section 4.3. To further compare the LM between \(kAnonymity\) and \(Est\_kAnonymity\), we plot the LM results in Figure 8b, where the x-axis represents the LM quantity for \(kAnonymity\) and the y-axis represents the LM quantity for \(Est\_kAnonymity\). Here, the red circles correspond to the overestimation cases, whereas the blue circles represent either the underestimation or corrected estimation cases. As can be seen in the figure, in most cases, the circles are located on the dotted diagonal line, which indicates that there is no loss in data utility with the proposed approach. Even under the occurrence of an overestimation, it is observed that the red circles are closely located on the diagonal line, indicating that the proposed approach does not cause a significant reduction in the information of the released microdata. Figure 8: (**a**) LM when varying the number of query results, and (**b**) comparison of LM between \(kAnonymity\) and \(Est\_kAnonymity\). Figure 7: The execution times when varying the number of query results. Figure 9 shows (a) the execution times and (b) loss metric (LM) for varying values of \(k\). During the experiments, the values of \(k\) varied among 3, 5, 9, and 13, and the values of \(min_{height}\) and \(max_{height}\) were set such that the number of query results was about 2.3 M. Key observations based on Figure 9 can be summarized as follows: as expected, the proposed method (\(Est\_KAnonymity\)) significantly outperforms the original \(k\)-anonymity algorithm (\(kAnonymity\)) in terms of the execution time. The performance gaps between \(Est\_kAnonymity\) and \(kAnonymity\) increase as the value of \(k\) increases. The figure also shows whether the generalization level for the \(k\)-anonymity is correctly estimated (i.e., 'C', 'U', and 'O').