On the comparison of microdata disclosure control algorithms

ABSTRACT

Privacy models such as k-anonymity and l-diversity typically offer an aggregate or scalar notion of the privacy property that holds collectively on the entire anonymized data set. However, they fail to give an accurate measure of privacy with respect to the individual tuples. For example, two anonymizations achieving the same value of k in the k-anonymity model will be considered equally good with respect to privacy protection. However, it is quite possible that for one of the anonymizations a majority of the individual tuples have lesser probabilities of privacy breaches than their counterparts in the other anonymization. We therefore reject the notion that all anonymizations satisfying a particular privacy property, such as k-anonymity, are equally good. The scalar or aggregate value used in privacy models is often biased towards a fraction of the data set, resulting in higher privacy for some individuals and minimalistic for others. Consequently, to better compare anonymization algorithms, there is a need to formalize and measure this bias. Towards this end, we advocate the use of vector-based methods for representing privacy and other measurable properties of an anonymization. We represent the measure of a given property for an anonymized data set using a property vector. Anonymizations are then compared using quality index functions that quantify the effectiveness of the property vectors. A formal analysis with respect to their scope and limitations is provided. Finally, we present preference based techniques when comparisons are to be made across multiple properties induced by anonymizations.

REFERENCES

• 1: 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]
• 2: Dewri, R., Ray, I., Ray, I., and Whitley, D. On the Optimal Selection of k in the k-Anonymity Problem. In Proceedings of the 24th International Conference on Data Engineering (Cancun, Mexico, 2008), pp. 1364--1366.
• 3: 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]
• 4: Hanse, M. P., and Jaszkiewicz, A. Evaluating the Quality of Approximations of the Non-dominated Set. IMM Technical Report IMM-REP-1998-7, Institute of Mathematical Modeling, Technical University of Denmark, 1998.
• 5: Huang, Z., and Du, W. OptRR: Optimizing Randomized Response Schemes for Privacy-Preserving Data Mining. In Proceedings of the 24th International Conference on Data Engineering (Cancun, Mexico, 2008), pp. 705--714.
• 6: Hundepool, A., and Willenborg, L. Mu and Tau Argus: Software for Statistical Disclosure Control. In Proceedings of the Third International Seminar on Statistical Confidentiality (Bled, Slovenia, 1996).
• 7: 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]
• 8: Knowles, J. D., and Corne, D. W. On Metrics for Comparing Non-Dominated Sets. In Proceedings of the Congress on Evolutionary Computation (Honolulu, HI, USA, 2002), pp. 711--716.
• 9: 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]
• 10: Li, N., Li, T., and Venkatasubramanian, S. t--Closeness: Privacy Beyond k--Anonymity and l-Diversity. In Proceedings of the 23rd International Conference on Data Engineering (Istanbul, Turkey, 2007), pp. 106--115.
• 11: Grigorios Loukides , Jianhua Shao, Capturing data usefulness and privacy protection in K-anonymisation, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244091]
• 12: Monte Lunacek , Darrell Whitley , Indrakshi Ray, A crossover operator for the k- anonymity problem, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144277]
• 13: 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]
• 14: M. Ercan Nergiz , Chris Clifton, Thoughts on k-anonymization, Data & Knowledge Engineering, v.63 n.3, p.622-645, December, 2007 [doi>10.1016/j.datak.2007.03.009]
• 15: 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]
• 16: 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]
• 17: 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]
• 18: Takemura, A. Local Recoding by Maximum Weight Matching for Disclosure Control of Microdata Sets. CIRJE F-Series CIRJE-F-40, CIRJE, Faculty of Economics, University of Tokyo, 1999.
• 19: Traian Marius Truta , Bindu Vinay, Privacy Protection: p-Sensitive k-Anonymity Property, Proceedings of the 22nd International Conference on Data Engineering Workshops, p.94, April 03-07, 2006 [doi>10.1109/ICDEW.2006.116]
• 20: 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
• 21: 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]
• 22: Jian Xu , Wei Wang , Jian Pei , Xiaoyuan Wang , Baile Shi , Ada Wai-Chee Fu, Utility-based anonymization using local recoding, 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.1150504]
• 23: Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., and da Fonseca, V. G. Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation 7, 2 (2003), 117--132.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Performance, Theory

Keywords:
anonymization bias, data privacy, performance evaluation