Abstract
Abstract Nowadays, data collection is an ongoing process, so personal privacy becomes more and more important. We need to publish data for purposes such as public health and demographic research. And some attributes which can clearly be used to identify individuals (such as name and medical record ID) are generally removed. Nevertheless, the database that people can sometimes join with other public databases on attributes (such as ZIP code, gender as well as age) to re-identify individuals can be called the “linking" attack. The way to protect individuals from re-identification is called “de-identification”. k-anonymity is an efficient way to prevent the linking attack by generalization or suppression so that no individual can be uniquely distinguished from a group of size k. In this thesis, we will discuss what k-anonymity is and find the minimal generalization in the sense of [13], described by Samarati. We will introduce the hash-based algorithm proposed by X. SUN, and propose a much more efficient as well as flexible algorithm that can be used to find the minimal generalization achieving k-anonymity.