Workload-aware anonymization

ABSTRACT

Protecting data privacy is an important problem in microdata distribution. Anonymization algorithms typically aim to protect individual privacy, with minimal impact on the quality of the resulting data. While the bulk of previous work has measured quality through one-size-fits-all measures, we argue that quality is best judged with respect to the workload for which the data will ultimately be used.This paper provides a suite of anonymization algorithms that produce an anonymous view based on a target class of workloads, consisting of one or more data mining tasks, as well as selection predicates. An extensive experimental evaluation indicates that this approach is often more effective than previous anonymization techniques.

References

1. C. Aggarwal and P. Yu. A condensation approach to privacy-preserving data mining. In EDBT, 2004.
2. G. Aggarwal, T. Feder, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu. Anonymizing tables. In ICDT, 2005.
3. R. Agrawal, S. Ghosh, T. Imielinski, and A. Swami. Database mining: A performance perspective. In IEEE Transactions on Knowledge and Data Engineering, volume 5, 1993.
4. R. Agrawal and R. Srikant. Privacy-preserving data mining. In SIGMOD, 2000.
5. R. Bayardo and R. Agrawal. Data privacy through optimal k-anonymization. In ICDE, 2005.
6. C. Blake and C. Merz. UCI repository of machine learning databases, 1998.
7. L. Breiman, J. Freidman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth International Group, Belmont, CA, 1984.
8. S. Chawla, C. Dwork, F. McSherry, and K. Talwar. On the utility of privacy-preserving histograms. In Uncertainty in Artificial Intelligence, 2005.
9. B. Chen, L. Chen, Y. Lin, and R. Ramakrishnan. Prediction cubes. In VLDB, 2005.
10. J. Domingo-Ferrer and J. Mateo-Sanz. Practical data-oriented microaggregation for statistical disclosure control. IEEE Transactions on Knowledge and Data Engineering, 4(1), 2002.
11. A. Evfimievski, R. Srikant, R. Agrawal, and J. Gehrke. Privacy preserving mining of association rules. In SIGKDD, 2002.
12. U. M. Fayyad and K. Irani. On the handling of continuous-valued attributes in decision tree generation. Machine Learning, 8:87--102, 1992.
13. B. Fung, K. Wang, and P. Yu. Top-down specialization for information and privacy preservation. In ICDE, 2005.
14. J. Gehrke, R. Ramakrishnan, and V. Ganti. RainForest: A framework for fast decision tree construction of large datasets. In VLDB, 1998.
15. V. Iyengar. Transforming data to satisfy privacy constraints. In ACM SIGKDD, 2002.
16. K. LeFevre, D.DeWitt, and R. Ramakrishnan. Incognito: Efficient full-domain k-anonymity. In ACM SIGMOD, 2005.
17. K. LeFevre, D. DeWitt, and R. Ramakrishnan. Mondrian multidimensional k-anonymity. In ICDE, 2006.
18. A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-Diversity: Privacy beyond k-anonymity. In ICDE, 2006.
19. A. Meyerson and R. Williams. On the complexity of optimal k-anonymity. In PODS, 2004.
20. S. Reiss. Practical data-swapping: The first steps. ACM Transactions on Database Systems, 9:20--37, 1984.
21. S. Rizvi and J. R. Haritsa. Maintaining data privacy in association rule mining. In VLDB, 2002.
22. P. Samarati. Protecting respondents' identities in microdata release. IEEE Trans. on Knowledge and Data Engineering, 13(6), 2001.
23. L. Sweeney. Achieving k-anonymity privacy protection using generalization and suppression. Int'l Journal on Uncertainty, Fuzziness, and Knowledge-based Systems, 10(5):571--588, 2002.
24. K. Wang, P. Yu, and S. Chakraborty. Bottom-up generalization: A data mining solution to privacy protection. In ICDM, 2004.
25. I. Witten and E. Frank. Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, San Francisco, 2nd edition, 2005.
26. J. Zhang and V. Honavar. Learning decision tree classifiers from attribute value taxonomies and partially specified data. In ICML, 2003.

Index Terms

• Information systems

  • Information systems applications