Injecting utility into anonymized datasets

ABSTRACT

Limiting disclosure in data publishing requires a careful balance between privacy and utility. Information about individuals must not be revealed, but a dataset should still be useful for studying the characteristics of a population. Privacy requirements such as k-anonymity and l-diversity are designed to thwart attacks that attempt to identify individuals in the data and to discover their sensitive information. On the other hand, the utility of such data has not been well-studied.In this paper we will discuss the shortcomings of current heuristic approaches to measuring utility and we will introduce a formal approach to measuring utility. Armed with this utility metric, we will show how to inject additional information into k-anonymous and l-diverse tables. This information has an intuitive semantic meaning, it increases the utility beyond what is possible in the original k-anonymity and l-diversity frameworks, and it maintains the privacy guarantees of k-anonymity and l-diversity.

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: Charu C. Aggarwal, On k-anonymity and the curse of dimensionality, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: G. Aggarwal, T. Feder, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu. Approximation algorithms for k-anonymity. Journal of Privacy Technology (JOPT), 2005.
• 4: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 5: 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
• 6: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 7: Adam L. Berger , Vincent J. Della Pietra , Stephen A. Della Pietra, A maximum entropy approach to natural language processing, Computational Linguistics, v.22 n.1, p.39-71, March 1996
• 8: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 9: S. Chawla, C. Dwork, F. McSherry, A. Smith, and H. Wee. Toward privacy in public databases. In Theory of Cryptography Conference, 2005.
• 10: Ronald Christensen. Log-Linear Models and Logistic Regression. Springer-Verlag, 1997.
• 11: L. H. Cox. Suppression, methodology and statistical disclosure control. Journal of the American Statistical Association, 75, 1980.
• 12: T. Dalenius and S. Reiss. Data swapping: A technique for disclosure control. Journal of Statistical Planning and Inference, 6:73--85, 1982.
• 13: Amol Deshpande , Minos N. Garofalakis , Michael I. Jordan, Efficient Stepwise Selection in Decomposable Models, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.128-135, August 02-05, 2001
• 14: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 15: A. Dobra. Statistical Tools for Disclosure Limitation in Multiway Contingency Tables. PhD thesis, CMU, 2002.
• 16: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 17: 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]
• 18: Finn Verner Jensen and Frank Jensen. Optimal junction trees. In UAI, pages 360--366, 1994.
• 19: 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]
• 20: S. L. Lauritzen. Graphical Models. Oxford Science Publications, 1996.
• 21: 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]
• 22: Jesus De Loera , Shmuel Onn, The Complexity of Three-Way Statistical Tables, SIAM Journal on Computing, v.33 n.4, p.819-836, 2004 [doi>10.1137/S0097539702403803]
• 23: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 24: Francesco M. Malvestuto. Approximating discrete probability distributions with decomposable models. IEEE Transactions on systems, Man and Cybernetics, 21(5):1287--1294, 1991.
• 25: 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]
• 26: Gerome Miklau , Dan Suciu, A formal analysis of information disclosure in data exchange, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007633]
• 27: Richard E. Neapolitan. Learning Bayesian Networks. Prentice Hall, December 2000.
• 28: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 29: U.C.Irvine Machine Learning Repository. http://www.ics.uci.edu/ mlearn/mlrepository.html.
• 30: 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]
• 31: P. Samarati and L. Sweeney. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. Technical report, CMU, SRI, 1998.
• 32: Sunita Sarawagi. User-adaptive exploration of multidimensional data. In VLDB, 2000.
• 33: 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]
• 34: Ke Wang , Benjamin C. M. Fung , Philip S. Yu, Template-Based Privacy Preservation in Classification Problems, Proceedings of the Fifth IEEE International Conference on Data Mining, p.466-473, November 27-30, 2005 [doi>10.1109/ICDM.2005.142]
• 35: Nanny Wermuth. Model search among multiplicative models. Biometrics, 1976.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.0 General

General Terms:
Design

Keywords:
k-anonymity, graphical models, l-diversity, loglinear models, marginals