## 4 Efficient Support of Online Data Publishing
### Phase I: Estimating the Generalization Level
Then, given selectivity ratios, \(s_{1},s_{2},\cdots,s_{l}\), computed as explained previously, the query result size is estimated as:  
\[|R_{res}|=|R|\times s_{1}\times s_{2}\times\cdots\times s_{l}.\]  
That is, based on the assumption of attribute value independence, the query result size is computed by the product of all selectivity ratios, \(s_{1},s_{2},\cdots,s_{l}\). Once the number of query results is computed, we next estimate the generalization level to achieve the \(k\)-anonymity property over the query results. Given a projection list, \(proj\_list\), of a query, let \(Q_{proj}=\{A_{1}^{\prime},A_{2}^{\prime},\cdots,A_{y}^{\prime}\}\) be the set of quasi-identifier attributes in \(proj\_list\) (where \(Q_{proj}\subset Q\)). Let us further assume that \(L(N,E)\) be a generalization lattice constructed with the attributes in \(Q_{proj}\), where \(N\) and \(E\) are the set of nodes and edges, respectively. The set of possible values for the quasi-identifier attributes in \(Q_{proj}\) at the specific node \(n_{i}\in N\) is then defined as follows:  
\[EQ_{n_{i}}=\{(v_{1},v_{2},\cdots,v_{y})\ |\ v_{1}\in V_{A_{1}^{\prime}},\ v_{2} \in V_{A_{2}^{\prime}},\ldots,v_{y}\in V_{A_{y}^{\prime}}\}.\]  
Here, \(V_{A_{i}^{\prime}}\) (\(1\leq t\leq y\)) is the set of possible values for the quasi-identifier attribute, \(A_{t}^{\prime}\), at node \(n_{i}\). Note that each possible value combination in \(EQ_{n_{i}}\) indeed corresponds to an equivalence class in the \(k\)-anonymity algorithm. **Example 1**. : _Let us consider the example shown in Figure 3, where \(Q_{proj}=\{Age,Zip\}\). Let \(n_{5}\) be a node associated with \(\langle O_{1},P_{1}\rangle\). The set of possible values for the quasi-identifier attributes, Age and Zip, at \(n_{5}\) is as follows:_  
\[V_{Age}=\{\text{10--20, 21--30}\},V_{Zip}=\{\text{306--3070, 3071--3080}\}.\]  
_Then, \(EQ_{n_{5}}\) is computed as follows:_  
\[EQ_{n_{5}}=\{(\text{10--20,306--3070}),\text{(10--20,3071--3080)},\text{(21--30,306 --3070)},\text{(21--30,3071--3087)}\}.\]_Each element in \(EQ_{n_{5}}\) corresponds to an equivalence class at the node \(n_{5}\) in the generalization lattice._  
Given a result relation, \(R_{res}\), and a node, \(n_{i}\), in a generalization lattice, let \(R_{res}[v_{1},v_{2},\cdots,v_{y}]\) be an equivalence class whose values correspond to \((v_{1},v_{2},\cdots,v_{y})\in EQ_{n_{i}}\) at node \(n_{i}\). The size of an equivalence class is then estimated as:  
\[|R_{res}[v_{1},v_{2},\cdots,v_{y}]|=|R_{res}|\times s_{(A^{\prime}_{1}=v_{1})} \times s_{(A^{\prime}_{2}=v_{2})}\times\cdots\times s_{(A^{\prime}_{y}=v_{y})}.\]  
Here, \(s_{(A^{\prime}_{i}=v_{i})}\) (\(1\leq t\leq y\)) is the selectivity ratio associated with the quasi-identifier attributes \(A^{\prime}_{t}\) and the value \(v_{t}\). Note that \(s_{(A^{\prime}_{t}=v_{t})}\) is estimated by leveraging a histogram, \(H(A^{\prime}_{t})\). **Example 2**. : _Let us continue with the example in Figure 3. \(|R_{res}[(10-20,3071-3080)]|\) is computed as:_  
\[s_{u}=\frac{f_{j}}{|R|}\times\frac{1}{d\sigma_{j}}.\]0  
_Here, \(s_{(Age=10-20)}\) corresponds to the selectivity ratio associated with \(\sigma_{10\leq Age\leq 20}(R)\), which is computed using a histogram, \(H(Age)\), as described earlier. Similarly, \(s_{(Zip=3071-3080)}\) can be computed using a histogram \(H(Zip)\)._  
\(K\)-anonymity is achieved if each equivalence class contains at least \(k\)-tuples. Thus, given node \(n_{i}\) in a generalization lattice, our approach checks whether the equivalence class having the minimum size satisfies the \(k\)-anonymity property as follows:  
\[s_{u}=\frac{f_{j}}{|R|}\times\frac{1}{d\sigma_{j}}.\]1  
Thus, our approach traverses each node of a generalization lattice in a bottom-up manner, such as in [2], until a node that satisfies the above equation is found. Our approach is similar to the algorithm in [2] in that the generalization lattice is traversed in a bottom-up manner.