There are many occasions when datasets containing person-specific information have to be published or communicated to untrusted parties in order to support, for example, intended research studies. In all such cases, existing privacy laws--both in the US and the EU--require that the data be published in an anonymous form. To facilitate data anonymization, several interesting algorithms have been proposed in the last few years that aim to find a good balance between the conflicting goals of data privacy and data utility, while minimizing the information loss incurred due to the anonymization process.

This paper proposes several O(log k)-approximation algorithms for achieving k-anonymity by attribute-values generalization through the use of hierarchies. The authors develop O(&bgr; log k)-approximation algorithms whose runtime can be adjusted based on the user-specified parameter &bgr; that sets the tolerance of the approximation ratio. The experimental evaluation of the proposed algorithms demonstrates that these approaches achieve better performance than traditional approaches, both in terms of approximation ratios and execution time.

The paper is generally well structured and written, with several examples that help the reader gain a good understanding of the details of the proposed methodologies. The algorithms are extensively evaluated against other state-of-the-art methods for local recoding, under various settings, and on four different real-life datasets.