# Enhancing Utility in Anonymized Data against the Adversary's Background Knowledge
## 2 Related Work
### Creation of the Initial QI Groups  
At first, the \(t\)-\(k\)-Utility algorithm generates a sorted list, \(\pi\), of complete records in \(N_{i}\) (Line 3 in Algorithm 2). The \(t\)-\(k\)-Utility uses the nearest point next (NPN) technique [9] to create the list (After evaluating various techniques to create an ordered list of records based on QI values, including space-filling curves [6], we found that the experimental results were consistent for both the adult dataset and the BKseq dataset). It sorts the records according to the QI values. The \(t\)-\(k\)-Utility algorithm follows a two-step process to ensure privacy and limit distortion caused by generalizing QI values. First, it creates primary QI groups by selecting the first \(k\) records as group q and checks if \(t\)-closeness is met. If not, it adds the next record to q and repeats the process until \(t\)-closeness is achieved (Lines 6 to 12 in Algorithm 2). Second,the algorithm attempts to add each record to an existing QI group, q', while maintaining \(t\)-closeness, and removes any records that cannot be placed in a group (Lines 13 to 21 in Algorithm 2). If \(t\)-closeness cannot be achieved, other solutions may be considered [6]. ``` Input: \(N_{i}\): The set of records; \([A_{0+1}|_{N_{i}}\): Domain of sensitive value in \(N_{i}\); \(Pr\): Distribution of sensitive values in T; \(k\) and \(t\): The parameters in privacy model Output:  A set of QI groups satisfying privacy model \(1\)// Step 1: To Create initial QI groups of \(N_{i}\) as \(\{q_{1},q_{2},\ldots,q_{c}\}\) \(2\)Qtemp \(\leftarrow\)\(\emptyset\)// a set of primary QI groups \(3\)\(\pi\)\(\leftarrow\) Create an order of all \(|N_{i



### Efficiency of the Proposed Anonymization Algorithm

The proposed anonymization algorithm includes two steps: BK-based clustering and the \(t\)-\(k\)-Utility approach. BK-based clustering applies agglomerative clustering and outputs a set of clusters, \(N=\{N_{1},\ldots,N_{|N|}\}\). The analysis of the algorithm shows that agglomerative clustering is a time-consuming component. Its worst-case time complexity is \(O(n^{2}logn)\) when \(n\) is the number of records in the original microdata. Then, we should apply \(t\)-\(k\)-Utility for each cluster \(N_{i}\)\(\in\)\(N\). In the first step of \(t\)-\(k\)-Utility, the NPN method has an \(O(|N_{i}|^{2})\) time complexity, and the worst-case running time of the second step of \(t\)-\(k\)-Utility is also \(O(|N_{i}|^{2})\). Hence, the time complexity of the proposed algorithm is \(O(n^{2}logn+\sum_{N_{i}\in N}O(|N_{i}|^{2}))\). In the worst case, BK-based clustering creates a cluster with the size \(n\). So, the worst-case time complexity of the proposed algorithm will be \(O(n^{2}logn+n^{2})\). ## 5 Experimental Result

In the following section, we will conduct an empirical evaluation of the proposed algorithm using two different datasets and various analysis measures. Section 5.1 explains the experiments' configuration and datasets, and Section 5.2 presents the evaluation criteria. Finally, Section 5.3 shows the evaluation results for the proposed algorithm. ### Evaluation Datasets and Configuration

To assess the efficacy of our proposed algorithms, we conducted several experiments using a machine equipped with a 2.5 GHz Intel Core i7 processor and 8 GB RAM. For implementing the hierarchical dendrogram, we utilized the linkage function provided by MATLAB (version R2022a). The distance between two clusters is measured using the complete linkage method. We conducted experiments with various values of privacy parameters (J, \(k\), and \(t\)) to evaluate the effectiveness of our proposed algorithms. The values for the model parameters were selected based on the policies of the data domain. To compare our algorithm with other similar studies [6; 12], we took the value of J, \(k\), and \(t\) in the ranges of 0.2-0.8, 3-20, and 0.5-0.8. It should be noted that each experiment was executed ten times, and the average of results is reported for smooth graph display.