# Enhancing Utility in Anonymized Data against the Adversary's Background Knowledge
## 2 Related Work
### Creation of the Initial QI Groups
#### 5.3.1 R-U Confidentiality Map

We investigated how varying the privacy parameters affects RL and GCP generated by three different algorithms, UHRA, BKA-JS, and \(k\)-primacy. First, we assumed that \(t\) and J were set to 0.5 and 0.8. The evaluation results of 3 algorithms using adult and BKseq datasets are shown in Figure 1, when \(k\) varies from 3 to 20. BKA-JS creates a sorted list of records based on the Hilbert index of QI values. The algorithm selects the first \(k\) records in the list and checks if the JSD values and \(k\)-closeness are below thresholds J and \(t\). Then, \(k\)-primacy generates groups where the difference between BK distributions does not exceed a threshold J. All three algorithms try to maximize the homogeneity of QI values in QI groups. As seen in Figure 1a, the BKA-JS algorithm results in higher information and privacy losses. The experimental results display that UHRA outperforms BKA-JS and \(k\)-primacy due to lower information loss. This result is because UHRA inserts one record into the existing QI groups until \(t\)-closeness is met. It then refines the initial QI groups to satisfy the privacy model with homogenous QI values. Our proposed algorithm has the best results with regard to privacy loss too. The results of evaluating the algorithms' performance on the BKseq dataset shown in Figure 1b confirm the findings. Subsequently, we evaluated the algorithms' performance across multiple values of J, with the parameters \(t\) and \(k\) fixed at 0.5 and 5, respectively. The value of the J parameter changes in the range of 0.2-0.8. The experimental results presented in Figure 2 restated our previous findings. UHRA results in QI groups with lower RL in both datasets, while the BKA-JS algorithm results in high RL and high privacy loss. In the next set of experiments, we analyzed the behavior of our algorithm as \(k\) and J were fixed. In the analysis, the \(t\) values vary in the range 0.5-0.8 and J and \(k\) were set to 0.8 and 5. As seen in Figure 3, The experimental results on both datasets affirm previous findings. Therefore, it can be concluded that the UHRA algorithm results in less information loss and better privacy in its output. In each level of RL, both BKA-JS and \(k\)-primacy result in higher information loss. Although both \(k\)-primacy and BKA-JS try to take records with similar QI values to enhance data utility, UHRA outperforms them regarding privacy and information loss. The refinement of the QI groups in UHRA results in lower information loss and higher data utility. Figure 1: R-U Map regarding various \(k\) values. Figure 3: R-U map regarding various \(t\) values. Figure 2: R-U map with regards to various J values. #### 5.3.2 Actual QI Group Size

This section presents how close to \(k\) the sizes of QI groups created by algorithms on the Adult dataset are. To minimize information loss and enhance data utility, QI groups with sizes close to \(k\) are better. At first, we assume that J and \(t\) are constant. The actual size of QI groups is shown in Table 3 over different values of \(k\). Each row presents the minimum and the average size of QI groups over different values of \(k\). The minimum size of QI groups determines the level of \(k\)-anonymity. As seen in Table 3, an increase in \(k\) values will increase the average size of QI groups. In addition, our algorithm's average size of QI groups is less than BKA-JS and \(k\)-primacy. Moreover, the difference between the average and the minimum size of QI groups in BKA-JS is more than other algorithms. We conclude that our proposed algorithm creates smaller QI groups compared to BKA-JS and \(k\)-primacy. We then investigate the size of quasi-identifier (QI) groups generated by the algorithms in Table 4, while holding the parameters \(k\) and \(t\) constant. Each row in the table reports the minimum and average size of QI groups for various J values. The findings confirm earlier observations that increasing J leads to larger QI groups on average.