## 4 Efficient Support of Online Data Publishing
### Phase III: Aggregating (and Further Anonymizing) Locally Anonymized Results  
In the final phase, the master node aggregates the anonymized results from every slave node. Because the method proposed in this paper estimates the generalization level of each quasi-identifier attribute based on the histograms, the aggregated results may not satisfy the \(k\)-anonymity requirement when either an under- or overestimation occurs. An underestimation corresponds to a case in which a node in the generalization lattice, which is estimated by the algorithm described in Section 4.1, is located before the set of nodes in the traversing order of the lattice node, where \(k\)-anonymity with minimal generalizations is achieved. Similarly, an overestimation is defined as a case in which an estimated node in a generalization lattice is located after the set of nodes in the traversing order of the lattice node, where \(k\)-anonymity with minimal generalizations is satisfied.  
For example, in Figure 5(a), let us assume that \(k\)-anonymity with minimal generalizations is achieved with the node \(\langle O_{0},P_{2}\rangle\), which is highlighted with the red oval. Furthermore, let assume that the generalization lattice is traversed in a bottom-up manner and nodes in the same label are traversed from left to right. In this example, the nodes \(\langle O_{2},P_{0}\rangle\), which are estimated using the algorithm described in Section 4.1, correspond to an underestimation case. On the other hand, the estimated node \(\langle O_{2},P_{1}\rangle\) is an overestimation case.  
Hence, after aggregating the anonymized results from every slave node, the master node needs to check whether \(k\)-anonymity is satisfied over the aggregated results. If so, the aggregated results are returned to the user. However, if \(k\)-anonymity is not satisfied owing to an underestimation of the generalization level of each quasi-identifier attribute, the master node needs to conduct further anonymization of the aggregated results until \(k\)-anonymity is satisfied. It should be noted that, even in such a situation, the proposed method is more efficient than the baseline approach (i.e., the global approach shown in Figure 3(a)), because the nodes in the generalization lattice that were already visited during the generalization estimation phase in Section 4.1 can be skipped during the anonymization process of the master node. For example, consider the underestimation example in Figure 5(b), in which the algorithm described in Section 4.1 estimates that the \(k\)-anonymity requirement is satisfied with the node \(\langle O_{2},P_{0}\rangle\), even though in reality it is not. In this case, the master node conducts the anonymization process on the actual aggregated results, starting from the node \(\langle O_{1},P_{1}\rangle\), and thus skips the nodes that were already visited during Phase I. This anonymization process continues until \(k\)-anonymity is satisfied. In the example in Figure 5(b), the anonymization process stops at the nodes \(\langle O_{0},P_{2}\rangle\), where \(k\)-anonymity is satisfied.  
By contrast, an overestimation causes a loss of information of the released micro-data because the quasi-identifier attributes are more generalized than necessary. With the anonymized results received from the slave nodes, the master node cannot detect whether an overestimation actually occurs, which results in returning more coarse-grained \(k\)-anonymity results to the user. This, in turn, leads to a loss in the data utility of the released microdata. That is, the algorithm proposed in this paper achieves a high level of efficiency in terms of applying \(k\)-anonymity by trading information loss with efficiency. However, as described in the experiment section, the proposed approach does not cause a significant reduction in the information on the released microdata, despite the occurrence of an overestimation, while achieving a high level of efficiency.