Home   >   CSC-OpenAccess Library   >    Manuscript Information
Query Processing with k-Anonymity
Mohamed Eltabakh, Jalaja Padma, Yasin N. Silva, Walid G. Aref, Pei He
Pages - 48 - 65     |    Revised - 15-03-2012     |    Published - 16-04-2012
Volume - 3   Issue - 2    |    Publication Date - April 2012  Table of Contents
Data Privacy, K-Anonimity, Query Processing, Database Management Systems
Anonymization techniques are used to ensure the privacy preservation of the data owners, especially for personal and sensitive data. While in most cases, data reside inside the database management system; most of the proposed anonymization techniques operate on and anonymize isolated datasets stored outside the DBMS. Hence, most of the desired functionalities of the DBMS are lost, e.g., consistency, recoverability, and efficient querying. In this paper, we address the challenges involved in enforcing the data privacy inside the DBMS. We implement the k-anonymity algorithm as a relational operator that interacts with other query operators to apply the privacy requirements while querying the data. We study anonymizing a single table, multiple tables, and complex queries that involve multiple predicates. We propose several algorithms to implement the anonymization operator that allow efficient non-blocking and pipelined execution of the query plan. We introduce the concept of k-anonymity view as an abstraction to treat k-anonymity (possibly, with multiple k preferences) as a relational view over the base table(s). For non-static datasets, we introduce the materialized k-anonymity views to ensure preserving the privacy under incremental updates. A prototype system is realized based on PostgreSQL with extended SQL and new relational operators to support anonymity views. The prototype system demonstrates how anonymity views integrate with other privacy- preserving components, e.g., limited retention, limited disclosure, and privacy policy management. Our experiments, on both synthetic and real datasets, illustrate the performance gain from the anonymity views as well as the proposed query optimization techniques under various scenarios.
CITED BY (1)  
1 Asayesh, A., Hadavi, M. A., & Jalili, R. (2015). (t, k)-Hypergraph anonymization: an approach for secure data publishing. Security and Communication Networks, 8(7), 1306-1317.
1 Google Scholar 
2 CiteSeerX 
3 Scribd 
4 SlideShare 
5 PdfSR 
Agarwal, R., Ameet Kini, Kristen LeFevre, Amy Wang, Yirong Xu, and Diana Zhou. Managing Healthcare Data Hippocratically. SIGMOD, 2004.
Agarwal, R., Kiernan, J., Ramakrishnan Srikant, and Yirong Xu. Hippocratic Databases. VLDB. 2002.
Agarwal, R., Paul, B., Grandison, T., Kiernan, J., Logan, S. and Rjaibi, W. Extending Relational Database Systems to Automatically Enforce Privacy Policies. ICDE. 2005.
Agrawal, R., Bayardo, R., Faloutsos, C., Kiernan, J., Rantzau, R., and Srikant, R. Auditing Compliance with a Hippocratic Database. VLDB. 2004.
Byun, J., Karma, A., Bertino, E., and Li, N. Efficient k-Anonymization using Clustering Techniques. DASFAA. 2007.
Chaudhuri, S., Dutta, T. and Sudarshan, S. Fine Grained Authorization Through Predicated Grants. ICDE, 2007.
Cranor, L., Langheinrich, M., Marchiori, M., Pressler-Marshall, M., and Reagle, J. The platform for privacy preferences 1.0 (P3P1.0) specification. W3C Recommendation, 2002.
Frank D. McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. SIGMOD, 2009
Jian Pei., Xu, J., Wang, Z., Wang, W., Wang, K., Maintaining K-Anonymity against Incremental Updates. 19th International Conference on Scientific and Statistical Database Management, 2007.
Laura-Silva, Y N., and Aref, W. Realizing Privacy-Preserving Features in Hippocratic Databases. ICDE. 2007.
LeFevre, K, Agarwal, R., Ercegovac, V., Ramakrishnan, R., Xu, Y. Limiting Disclosure in Hippocratic Databases. VLDB. 2004.
Li, N., Li, T., and Venkatasubramanian, S. t-closeness: Privacy Beyond k-Anonymity and l- Diversity. ICDE. 2007.
Machanavajjhala, A., Gherke, J., Kifer, D., and Venkitasubramaniam, M. l-Diversity: Privacy beyond k-Anonymity. ICDE. 2006.
Nergiz, Ercan M, Clifton, C., and Nergiz, A E . Multi-relational k-Anonymity. ICDE. 2007.
Padma, J., Silva, Y., Arshad, U., Aref, W. G. Hippocratic PostgreSQL. ICDE. 2009.
Qihua Wang et al. On the Correctness Criteria of Fine-Grained Access Control in Relational Databases.VLDB.’07.
Sweeney, L. Achieving k-anonymity privacy protection using generalization and suppression. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, ‘02.
Sweeney, L. Guaranteeing anonymity when sharing medical data, the datafly system. Journal of the American Medical Informatics Association, 1997.
Sweeney, L. k-Anonymity:A model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 2002.
Truta, Traian Marius, and Alina Campan. K-Anonymization Incremenatal Maintenance and Optimization Techniques. Symposium on Applied Computing. 2007.
Xiao, Xiaokui, and Yufei Tao. Personalized Privacy Preservation. SIGMOD, 2006.
Xu, Jian, Wei Wang, Jian Pei, Xiaoyuan Wang, Baile Shi, and Ada Wai-Chee Fu. Utility-based Anonymization using Local Recoding. KDD. 2006.
Professor Mohamed Eltabakh
WPI - United States of America
Miss Jalaja Padma
Cisco Systems - United States of America
Mr. Yasin N. Silva
- United States of America
Professor Walid G. Aref
Purdue University - United States of America
Mr. Pei He
Purdue University - United States of America

View all special issues >>