Anonymized data: generation, models, usage

ABSTRACT

Data anonymization techniques have been the subject of intense investigation in recent years, for many kinds of structured data, including tabular, graph and item set data. They enable publication of detailed information, which permits ad hoc queries and analyses, while guaranteeing the privacy of sensitive information in the data against a variety of attacks. In this tutorial, we aim to present a unified framework of data anonymization techniques, viewed through the lens of uncertainty. Essentially, anonymized data describes a set of possible worlds, one of which corresponds to the original data. We show that anonymization approaches such as suppression, generalization, perturbation and permutation generate different working models of uncertain data, some of which have been well studied, while others open new directions for research. We demonstrate that the privacy guarantees offered by methods such as k-anonymization and l-diversity can be naturally understood in terms of similarities and differences in the sets of possible worlds that correspond to the anonymized data. We describe how the body of work in query evaluation over uncertain databases can be used for answering ad hoc queries over anonymized data in a principled manner. A key benefit of the unified approach is the identification of a rich set of new problems for both the Data Anonymization and the Uncertain Data communities.

REFERENCES

• 1: Serge Abiteboul , Paris Kanellakis , Gösta Grahne, On the representation and querying of sets of possible worlds, Theoretical Computer Science, v.78 n.1, p.159-187, Jan. 21, 1991
• 2: Charu C. Aggarwal, On Unifying Privacy and Uncertain Data Models, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.386-395, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497447]
• 3: Lars Backstrom , Cynthia Dwork , Jon Kleinberg, Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242598]
• 4: O. Benjelloun, A. D. Sarma, C. Hayworth, and J. Widomn. An introduction to ULDBs and the Trio system. IEEE Data Engineering Bulletin, 29(1): 5--16, Mar. 2006.
• 5: Justin Brickell , Vitaly Shmatikov, Efficient anonymity-preserving data collection, 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.1150415]
• 6: Graham Cormode , Divesh Srivastava , Ting Yu , Qing Zhang, Anonymizing bipartite graph data using safe groupings, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453947]
• 7: Michael Hay , Gerome Miklau , David Jensen , Don Towsley , Philipp Weis, Resisting structural re-identification in anonymized social networks, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453873]
• 8: Kun Liu , Evimaria Terzi, Towards identity anonymization on graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376629]
• 9: Ling Liu, From data privacy to location privacy: models and algorithms, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 10: 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]
• 11: 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]
• 12: Anish Das Sarma , Omar Benjelloun , Alon Halevy , Jennifer Widom, Working Models for Uncertain Data, Proceedings of the 22nd International Conference on Data Engineering, p.7, April 03-07, 2006 [doi>10.1109/ICDE.2006.174]
• 13: Dan Suciu , Nilesh Dalvi, Foundations of probabilistic answers to queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066303]
• 14: 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]
• 15: Manolis Terrovitis , Nikos Mamoulis , Panos Kalnis, Privacy-preserving anonymization of set-valued data, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453874]
• 16: Xiaokui Xiao , Yufei Tao, Anatomy: simple and effective privacy preservation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 17: Yabo Xu , Ke Wang , Ada Wai-Chee Fu , Philip S. Yu, Anonymizing transaction databases for publication, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401982]
• 18: Zhiqiang Yang , Sheng Zhong , Rebecca N. Wright, Anonymity-preserving data collection, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081909]
• 19: Q. Zhang, N. Koudas, D. Srivastava, and T. Yu. Aggregate query answering on anonymized tables. In IEEE International Conference on Data Engineering, 2007.
• 20: E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In International Workshop on Privacy, Security and Trust in KDD (PinKDD), 2007.
• 21: Bin Zhou , Jian Pei, Preserving Privacy in Social Networks Against Neighborhood Attacks, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.506-515, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497459]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

General Terms:
Algorithms, Security

Keywords:
anonymization, privacy, uncertain databases