Local and global recoding methods for anonymizing set-valued data

Manolis Terrovitis, Nikos Mamoulis, Panos Kalnis

Research output: Contribution to journalArticlepeer-review

84 Scopus citations


In this paper, we study the problem of protecting privacy in the publication of set-valued data. Consider a collection of supermarket transactions that contains detailed information about items bought together by individuals. Even after removing all personal characteristics of the buyer, which can serve as links to his identity, the publication of such data is still subject to privacy attacks from adversaries who have partial knowledge about the set. Unlike most previous works, we do not distinguish data as sensitive and non-sensitive, but we consider them both as potential quasi-identifiers and potential sensitive data, depending on the knowledge of the adversary. We define a new version of the k-anonymity guarantee, the k m-anonymity, to limit the effects of the data dimensionality, and we propose efficient algorithms to transform the database. Our anonymization model relies on generalization instead of suppression, which is the most common practice in related works on such data. We develop an algorithm that finds the optimal solution, however, at a high cost that makes it inapplicable for large, realistic problems. Then, we propose a greedy heuristic, which performs generalizations in an Apriori, level-wise fashion. The heuristic scales much better and in most of the cases finds a solution close to the optimal. Finally, we investigate the application of techniques that partition the database and perform anonymization locally, aiming at the reduction of the memory consumption and further scalability. A thorough experimental evaluation with real datasets shows that a vertical partitioning approach achieves excellent results in practice. © 2010 Springer-Verlag.
Original languageEnglish (US)
Pages (from-to)83-106
Number of pages24
JournalThe VLDB Journal
Issue number1
StatePublished - Jun 10 2010

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: We would like to thank the authors of [12] for sharing with us the implementation of the Partition algorithm. This work was supported by grant HKU 715108E from Hong Kong RGC.

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems


Dive into the research topics of 'Local and global recoding methods for anonymizing set-valued data'. Together they form a unique fingerprint.

Cite this