Workload-aware anonymization techniques for large-scale datasets

ABSTRACT

Protecting individual privacy is an important problem in microdata distribution and publishing. Anonymization algorithms typically aim to satisfy certain privacy definitions with minimal impact on the quality of the resulting data. While much of the previous literature has measured quality through simple 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 article provides a suite of anonymization algorithms that incorporate a target class of workloads, consisting of one or more data mining tasks as well as selection predicates. An extensive empirical evaluation indicates that this approach is often more effective than previous techniques. In addition, we consider the problem of scalability. The article describes two extensions that allow us to scale the anonymization algorithms to datasets much larger than main memory. The first extension is based on ideas from scalable decision trees, and the second is based on sampling. A thorough performance evaluation indicates that these techniques are viable in practice.

REFERENCES

• 1: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 2: Aggarwal, C. and Yu, P. 2004. A condensation approach to privacy-preserving data mining. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT).
• 3: Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., and Zhu, A. 2005. Anonymizing tables. In Proceedings of the 10th International Conference on Database Theory (ICDT).
• 4: Gagan Aggarwal , Tomás Feder , Krishnaram Kenthapadi , Samir Khuller , Rina Panigrahy , Dilys Thomas , An Zhu, Achieving anonymity via clustering, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142374]
• 5: R. Agrawal , T. Imielinski , A. Swami, Database Mining: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.914-925, December 1993 [doi>10.1109/69.250074]
• 6: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 7: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering, p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 8: Blake, C. and Merz, C. 1998. UCI repository of machine learning databases. University of California Irvine.
• 9: Avrim Blum , Cynthia Dwork , Frank McSherry , Kobbi Nissim, Practical privacy: the SuLQ framework, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065184]
• 10: Breiman, L., Freidman, J., Olshen, R., and Stone, C. 1984. Classification and Regression Trees. Wadsworth International Group, Belmont, CA.
• 11: Chawla, S., Dwork, C., McSherry, F., Smith, A., and Wee, H. 2005. Toward privacy in public databases. In Proceedings of the 2nd Theory of Cryptography Conference.
• 12: Bee-Chung Chen , Lei Chen , Yi Lin , Raghu Ramakrishnan, Prediction cubes, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: Bee-Chung Chen , Kristen LeFevre , Raghu Ramakrishnan, Privacy skyline: privacy with multidimensional adversarial knowledge, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 14: J. Domingo-Ferrer , J. M. Mateo-Sanz, Practical Data-Oriented Microaggregation for Statistical Disclosure Control, IEEE Transactions on Knowledge and Data Engineering, v.14 n.1, p.189-201, January 2002 [doi>10.1109/69.979982]
• 15: Dwork, C. 2006. Differential privacy. In Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming (ICALP).
• 16: Dwork, C., McSherry, F., Nissim, K., and Smith, A. 2006. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Conference.
• 17: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775080]
• 18: Benjamin C. M. Fung , Ke Wang , Philip S. Yu, Top-Down Specialization for Information and Privacy Preservation, Proceedings of the 21st International Conference on Data Engineering, p.205-216, April 05-08, 2005 [doi>10.1109/ICDE.2005.143]
• 19: Johannes Gehrke , Venkatesh Ganti , Raghu Ramakrishnan , Wei-Yin Loh, BOAT—optimistic decision tree construction, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.169-180, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 20: Johannes Gehrke , Raghu Ramakrishnan , Venkatesh Ganti, RainForest - A Framework for Fast Decision Tree Construction of Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.416-427, August 24-27, 1998
• 21: HIP. 2002. Standards for privacy of individuals identifiable health information. U.S. Department of Health and Human Services.
• 22: Tochukwu Iwuchukwu , Jeffrey F. Naughton, K-anonymization as spatial indexing: toward scalable and incremental anonymization, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 23: Vijay S. Iyengar, Transforming data to satisfy privacy constraints, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775089]
• 24: Krishnaram Kenthapadi , Nina Mishra , Kobbi Nissim, Simulatable auditing, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065183]
• 25: Daniel Kifer , Johannes Gehrke, Injecting utility into anonymized datasets, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142499]
• 26: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Incognito: efficient full-domain K-anonymity, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066164]
• 27: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
• 28: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Workload-aware anonymization, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150435]
• 29: Li, N., Li, T., and Venkatasubramanian, S. 2007. t-Closeness: Privacy beyond k-anonymity and l-diversity. In Proceedings of the IEEE International Conference on Data Engineering (ICDE).
• 30: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 31: Martin, D., Kifer, D., Machanavajjhala, A., Gehrke, J., and Halpern, J. 2007. Worst-case background knowledge in privacy. In Proceedings of the IEEE International Conference on Data Engineering (ICDE).
• 32: Adam Meyerson , Ryan Williams, On the complexity of optimal K-anonymity, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055591]
• 33: Nina Mishra , Mark Sandler, Privacy via pseudorandom sketches, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142373]
• 34: Mohamed F. Mokbel , Chi-Yin Chow , Walid G. Aref, The new Casper: query processing for location services without compromising privacy, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 35: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 36: Shariq J. Rizvi , Jayant R. Haritsa, Maintaining data privacy in association rule mining, Proceedings of the 28th international conference on Very Large Data Bases, p.682-693, August 20-23, 2002, Hong Kong, China
• 37: P. Samarati, Protecting Respondents' Identities in Microdata Release, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.1010-1027, November 2001 [doi>10.1109/69.971193]
• 38: Latanya Sweeney, Achieving k-anonymity privacy protection using generalization and suppression, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.571-588, October 2002 [doi>10.1142/S021848850200165X]
• 39: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 40: Ke Wang , Benjamin C. M. Fung, Anonymizing sequential releases, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150449]
• 41: Ke Wang , Philip S. Yu , Sourav Chakraborty, Bottom-Up Generalization: A Data Mining Solution to Privacy Protection, Proceedings of the Fourth IEEE International Conference on Data Mining, p.249-256, November 01-04, 2004
• 42: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 43: Xiaokui Xiao , Yufei Tao, Personalized privacy preservation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142500]
• 44: Xiaokui Xiao , Yufei Tao, M-invariance: towards privacy preserving re-publication of dynamic datasets, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247556]
• 45: Chao Yao , X. Sean Wang , Sushil Jajodia, Checking for k-anonymity violation by views, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 46: Zhang, J. and Honavar, V. 2003. Learning decision tree classifiers from attribute value taxonomies and partially specified data. In Proceedings of the 20th International Conference on Machine Learning (ICML).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
Databases, anonymity, data mining, performance, privacy, scalability