Abstract—k-anonymity is one of the most studied models of privacy preserving technology. It limits the linking confidence between specific sensitive information and a specific individual by hiding the identifications of each individual into at least k-1 others in the database. A k-anonymization algorithm is usually evaluated using information loss or data utility metrics. In this paper, we first propose a new quality metric, called the Efficiency metric. This metric overcomes the limitations of existing one dimensional metrics, representing either privacy measure or data utility measure, used in privacy preserving data sharing. We then present a new heuristic algorithm for k-anonymization that offers high data utility as well as a high level of privacy. Comparisons of experimental results of our algorithm with those of three other well-known algorithms for k-anonymity show that our algorithm performs the best both in terms of utility measure and privacy measure.
Index Terms—Anonymization, information loss, privacy, utility.
M. N. Huda is with the Research Organization of Information and Systems (ROIS), Tokyo, Japan (e-mail: email@example.com).
S. Yamada and N. Sonehara are with the National Institute of Informatics (NII), Tokyo, Japan (e-mail: firstname.lastname@example.org, email@example.com).
Cite: Md Nurul Huda, Shigeki Yamada, and Noboru Sonehara, "On Enhancing Utility in k-Anonymization," International Journal of Computer Theory and Engineering vol. 4, no. 4, pp. 527-532, 2012.