Privacy Hash Table

Abstract

A number of organizations publish microdata for purposes such as public health and demographic research. Although attributes of microdata that clearly identify individuals, such as name, are generally removed, these databases can sometimes be joined with other public databases on attributes such as Zip code, Gender, and Age to re-identify individuals who were supposed to remain anonymous. These linking attacks are made easier by the availability of other complementary databases over the Internet. K-anonymity is a technique that prevents linking attacks by generalizing or suppressing portions of the released microdata so that no individual can be uniquely distinguished from a group of size k. In this chapter, we investigate a practical full-domain generalization model of k-anonymity and examine the issue of computing minimal k-anonymous solution. We introduce the hash-based technique previously used in mining associate rules and present an efficient and effective privacy hash table structure to derive the minimal solution. The experimental results show the proposed hash-based technique is highly efficient compared with the binary search method.