# Enhancing Utility in Anonymized Data against the Adversary's Background Knowledge
## 2 Related Work
### Anonymization without Adversary's Background Knowledge  
The \(k\)-anonymity [7] and its refinements (\(t\)-closeness [8] and \(l\)-diversity [9]) are privacy models which divide the records into several QI groups. In \(k\)-anonymity, the possibility of identifying a record in a QI group is \(1/k\) at most. In \(t\)-closeness, the distance between the distribution of the sensitive values in each QI group and those in the total data is no more than a threshold \(t\) value. It should be noted that the refinements (such as \(l\)-diversity and \(t\)-closeness) cannot replace the \(k\)-anonymity approach. Several studies have suggested a combination of privacy mechanisms to prevent against attribute and identity attacks [6; 12; 14]. [PERSON] and [PERSON] [15] recognized some drawbacks of \(t\)-closeness that have attracted broad attention to prevent against attribute disclosure [5; 12; 16; 17; 18].  
Many different anonymization algorithms have been proposed for satisfying syntactic privacy models. The algorithms use anonymization operations, such as generalization [12; 19; 20; 21; 22; 23; 24], anatomy [16], and microaggregations [14; 17; 25]. The generalization refers to altering attribute values in microdata with a range of general values. For example, assume that Table 1 shows patient's data in a hospital. In Table 1, the microdata includes one record for each patient, called a record respondent. Each record in the dataset contains an identifier attribute (name), three quasi-identifier attributes (gender, age, and zip code), and a sensitive attribute (disease). Table 2 shows the corresponding generalized version of the data. An anonymization algorithm that uses generalization deletes identifiers and divides data into QI groups. The SA is published without a change to analyze the data.  
Table 2 satisfies the 3-anonymous model because if the adversary knows the QI values of a victim, without any additional knowledge, the adversary can find the victim's record and disease with a maximum probability of \(1/3\).  
A generalization operation is suitable for categorical data but cannot process numerical data with high accuracy. The anatomy operator results in more than one table and increases the difficulty of data processing and analysis. Microaggregation [17] is not suitable for categorical values. The synthetic records that are released no longer correspond to the actual values in the original dataset, rendering the released data meaningless. In contrast, the generalized data remain semantically compatible with the original raw data. However, due to the elimination of some values, the distribution of anonymous data using microaggregation may differ from that of the original data [12]. This work uses generalization due to its advantages over microaggregation and anatomy. It should be worth noting that each of these operations has its place in research.  
A close work to ours is probably the one in [6]. The algorithm creates a list of records according to the Hilbert index. With this technique, records with similar QI values are also close, with high probability. Each \(k\) record satisfying \(t\)-closeness is released as a QI group. If the condition is not met, other records are added to the QI group. The main problem of said algorithm is high information loss. Another work that is close to ours is the one in [12]. The algorithm satisfies both \(\beta\)-likeness [15] and \(k\)-anonymity. They suggested a hierarchical algorithm to meet privacy models. In the algorithm, \(k\)-anonymity has priority over \(\beta\)-likeness. The experimental result showed that data utility is low.