On optimal anonymization for l+-diversity
Authors:
- 1 January 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 213-224
Abstract
Publishing person specific data while protecting privacy is an important problem. Existing algorithms that enforce the privacy principle called l-diversity are heuristic based due to the NP-hardness. Several questions remain open: can we get a significant gain in the data utility from an optimal solution compared to heuristic ones; can we improve the utility by setting a distinct privacy threshold per sensitive value; is it practical to find an optimal solution efficiently for real world datasets. This paper addresses these questions. Specifically, we present a pruning based algorithm for finding an optimal solution to an extended form of the l-diversity problem. The novelty lies in several strong techniques: a novel structure for enumerating all solutions, methods for estimating cost lower bounds, strategies for dynamically arranging the enumeration order and updating lower bounds. This approach can be instantiated with any reasonable cost metric. Experiments on real world datasets show that our algorithm is efficient and improves the data utility.Keywords
This publication has 19 references indexed in Scilit:
- Maintaining K-Anonymity against Incremental Updates19th International Conference on Scientific and Statistical Database Management (SSDBM 2007), 2007
- Hiding the presence of individuals from shared databases2007
- Worst-Case Background Knowledge for Privacy-Preserving Data Publishing2007
- Aggregate Query Answering on Anonymized Tables2007
- L-diversity: privacy beyond k-anonymity2006
- Mondrian Multidimensional K-Anonymity2006
- Incognito2005
- On the complexity of optimal K-anonymity2004
- Transforming data to satisfy privacy constraints2002
- Optimization by Simulated AnnealingScience, 1983