# Enhancing Utility in Anonymized Data against the Adversary's Background Knowledge
## 2 Related Work
### Creation of the Initial QI Groups
Specifically, we note that the average size of QI groups produced by BKA-JS exceeds that of UHRA. Finally, we show how close to \(k\) are the sizes of the QI groups produced by algorithms over different values of \(t\). We assume that \(k\) and J are set to 5 and 0.8. The actual size of QI groups created by algorithms is presented in Table 5. Each table row shows the minimum and the average size of the QI groups when the \(t\) value varies from 0.5 to 0.8. The experimental results also confirm previous conclusions. We see that the average size of QI groups increases for different \(t\) values. #### 5.3.3 The Speed and Scalability

In this section, we analyze the runtime of the proposed algorithm on the BKseq dataset. To this end, \(k\) and \(t\) are set to 5 and 0.5, while J is taken in the range of 0.1-0.7. The runtime of algorithms for different J values is presented in Figure 4. In the figure, the vertical axis is on a logarithmic scale. Our experiments reveal that the runtime of our algorithms remains consistent for J values greater than or equal to 0.3. This result stems from the close \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Method**} & \multicolumn{2}{c}{**J = 0.2**} & \multicolumn{2}{c}{**J = 0.3**} & \multicolumn{2}{c}{**J = 0.4**} & \multicolumn{2}{c}{**J = 0.5**} & \multicolumn{2}{c}{**J = 0.6**} \\ \cline{2-10}  & **min** & **avg** & **min** & **avg** & **min** & **avg** & **min** & **avg** & **min** & **avg** \\ \hline
**UHRA** & **5** & **9** & **5** & **9** & **5** & **10** & **5** & **11** & **5** & **10** \\ \hline BKA-JS & 5 & 11 & 5 & 11.8 & 5 & 13 & 5 & 13 & 5 & 13 \\ \hline \(k\)-primacy & 5 & 10 & 5 & 11 & 5 & 12 & 5 & 12 & 5 & 12 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: The size (min, avg) of QI groups on Adult dataset with \(t\) = 0.5 and \(k\) = 5. \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Method**} & \multicolumn{2}{c}{\(k\) = 3} & \multicolumn{2}{c}{\(k\) = 5} & \multicolumn{2}{c}{\(k\) = 10} & \multicolumn{2}{c}{\(k\) = 15} & \multicolumn{2}{c}{\(k\) = 20} \\ \cline{2-10}  & **min** & **avg** & **min** & **avg** & **min** & **avg** & **min** & **avg** & **min** & **avg** \\ \hline
**UHRA** & **3** & **8** & **5** & **9** & **10** & **11** & **15** & **17** & **20** & **23** \\ \hline BKA-JS & 3 & 8.8 & 5 & 13 & 10 & 14 & 15 & 20 & 20 & 25 \\ \hline \(k\)-primacy & 3 & 8 & 5 & 11 & 10 & 14 & 15 & 18 & 20 & 24 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The size (min, avg) of QI groups on the adult dataset with \(t\) = 0.5 and J = 0.8. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Method**} & \multicolumn{2}{c}{\(t\) = 0.5} & \multicolumn{2}{c}{\(t\) = 0.6} & \multicolumn{2}{c}{\(t\) = 0.7} & \multicolumn{2}{c}{\(t\) = 0.8} \\ \cline{2-10}  & **min** & **avg** & **min** & **avg** & **min** & **avg** & **min** & **avg** & **min** & **avg** \\ \hline
**UHRA** & **5** & **9** & **5** & **10** & **5** & **11** & **5** & **11** \\ \hline BKA-JS & 5 & 13 & 5 & 13 & 5 & 15 & 5 & 17 \\ \hline \(k\)-primacy & 5 & 11 & 5 & 12 & 5 & 12 & 5 & 12.8 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: The size of QI groups on Adult dataset with J = 0.8 and \(k\) = 5.

proximity of background knowledge (BK) distributions among the records in the BKseq dataset and the first step of UHRA generating a single cluster for J values less than or equal to 0.3. Notably, our algorithm exhibits faster execution times for J values less than 0.3. Specifically, UHRA's initial step generates multiple small clusters for these J values, which results in fewer record movements between QI groups to satisfy the privacy constraints. We also see that the runtime of UHRA is higher than BKA-JS, but our algorithm is similar to \(k\)-primacy. Then, we select values of privacy parameters such that a worst-case execution time can be seen.