›› 2012, Vol. 27 ›› Issue (1): 24-36.doi: 10.1007/s11390-012-1203-6

• Artificial Intelligent and Pattern Recognition • Previous Articles     Next Articles

Publishing Set-Valued Data Against Realistic Adversaries

Jun-Qiang Liu (刘君强)   

  1. School of Information and Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China
  • Received:2011-07-11 Revised:2011-11-24 Online:2012-01-05 Published:2012-01-05
  • Supported by:

    This work is supported in part by the Natural Science Foundation of Zhejiang Provice of China under Grant No. Y105700, and the Science and Technology Development Plan of Zhejiang Province of China under Grant No. 2006C21034.

Privacy protection in publishing set-valued data is an important problem. However, privacy notions proposed in prior works either assume that the adversary has unbounded knowledge and hence provide over-protection that causes excessive distortion, or ignore the knowledge about the absence of certain items and do not prevent attacks based on such knowledge. To address these issues, we propose a new privacy notion, (k,l)(m,n)-privacy, which prevents both the identity disclosure and the sensitive item disclosure to a realistic privacy adversary who has bounded knowledge about the presence of items and the bounded knowledge about the absence of items. In addition to the new notion, our contribution is an efficient algorithm that finds a near-optimal solution and is applicable for anonymizing real world databases. Extensive experiments on real world databases showed that our algorithm outperforms the state of the art algorithms.

[1] Liu J, Pan Y, Wang K, Han J. Mining frequent item sets byopportunistic projection. In Proc. the 8th ACM SIGKDDConf. Knowledge Discovery and Data Mining, Edmonton,Canada, July 2002, pp.229-238.

[2] Narayanan A, Shmatikov V. How to break anonymity of theNetflix prize dataset. ArXiv Computer Science e-prints, Vol-ume: abs/cs/061, December 2005, pp.1-10.

[3] Adar E. User 4XXXXX9: Anonymizing query logs. In QueryLog Analysis Workshop at the 16th Int. World Wide WebConf., Banff, Canada, May 2007.

[4] Xiong L, Agichtein E. Towards privacy-preserving query logpublishing. In Query Log Analysis Workshop at Int. WorldWide Web Conf., Banff, Canada, May 2007.

[5] He Y, Naughton J. Anonymization of set-valued data via top-down, local generalization. In Proc. Very Large Data BasesConf., Lyon, France, August 2009, pp.934-945.

[6] Ghinita G, Tao Y, Kalnis P. On the anonymization of sparsehigh-dimensional data. In Proc. Int. Conf. Data Engineer-ing, Cancun, Mexico, April 2008, pp.715-724.

[7] Terrovitis M, Mamoulis N, Kalnis P. Privacy preservinganonymization of set-valued data. In Proc. the 34th VeryLarge Data Bases Conf., Auckland, New Zealand, Aug. 2008,pp.115-125.

[8] Xu Y, Wang K, Fu A, Yu P S. Anonymizing transactiondatabases for publication. In Proc. the 14th ACM SIGKDDConf. Knowledge Discovery and Data Mining, Las Vegas,USA, August 2008, pp.767-775.

[9] Samarati P, Sweeney L. Generalizing data to provideanonymity when disclosing information. In Proc. ACMSIGMOD-SIGACT-SIGART Symposium on Principles ofDatabase Systems, Seattle, USA, June 1998, p.188.

[10] Aggarwal C C. On k-anonymity and the curse of dimensiona-lity. In Proc. the 31st Very Large Data Bases Conf., Trond-heim, Norway, August 2005, pp.901-909.

[11] LeFevre K, DeWitt D, Ramakrishnan R. Mondrian multidi-mensional k-anonymity. In Proc. Int. Conf. Data Engineer-ing, Atlanta, USA, April 2006, pp.25.

[12] Liu J, Wang K. On optimal anonymization for `+-diversity.In Proc. Int. Conf. Data Engineering, Long Beach, USA,March 2010, pp.213-224.

[13] Machanavajjhala A, Gehrke J, Kifer D, VenkitasubramaniamM. `-Diversity: Privacy beyond k-anonymity. In Proc. Int.Conf. Data Engineering, Atlanta, USA, April 2006, p.24.

[14] Machanavajjhala A, Gehrke J, G?otz M. Data publishingagainst realistic adversaries. In Proc. Very Large Data BasesConf., Lyon, France, August 2009, pp.790-801.

[15] Martin D J, Kifer D, Machanavajjhala A, Gehrke J. Worst-case background knowledge for privacy preserving data pub-lishing. In Proc. Int. Conf. Data Engineering, Istanbul,Turkey, April 2007, pp.126-135.

[16] Cormode G, Srivastava D, Yu T, Zhang Q. Anonymizing bi-partite graph data using safe groupings. In Proc. the 34thVery Large Data Bases Conf., Auckland, New Zealand, Au-gust 2008, pp.833-844.

[17] Evfimievski A, Srikant R, Agrawal R, Gehrke J. Privacy pre-serving mining of association rules. In Proc. the 8th ACMSIGKDD Conf. Knowledge Discovery and Data Mining, Ed-monton, Canada, July 2002, pp.217-228.

[18] Verykios V S, Elmagarmid A K, Bertino E, Saygin Y, DasseniE. Association rule hiding. Trans. Knowledge and Data En-gineering, April 2004, 16(4): 434-447.

[19] Atzori M, Bonchi F, Giannotti F, Pedreschi D. Anonymitypreserving pattern discovery. VLDB Journal, July 2008,17(4):703-727.

[20] Dwork C. Differential privacy. In Proc. the 33rd Int. Col-loquium on Automata, Languages and Programming, Venice,Italy, July 2006, Part II, pp.1-12.

[21] Korolova A, Kenthapadi K, Mishra N, Ntoulas A. Releasingsearch queries and clicks privately. In Proc. Int. World WideWeb Conf., Madrid, Spain, April 2009, pp.171-180.

[22] Xiao Y, Xiong L, Yuan C. Differentially private data releasethrough multidimensional partitioning. In Secure Data Man-agement Workshop at Very Large Data Bases Conf., Singa-pore, September 2010, pp.150-168.

[23] Chen R, Mohammed N, Fung B C M, Desai B C, Xiong L.Publishing set-valued data via differential privacy. In Proc.the 37th Very Large Data Bases Conf., Seattle, USA, August2011, pp.1087-1098.

[24] Iyengar V. Transforming data to satisfy privacy constraints.In Proc. the 8th ACM SIGKDD Conf. Knowledge Discoveryand Data Mining, Edmonton, Canada, July 2002, pp.279-288.

[25] Xu J, Wang W, Pei J, Wang X, Shi B, Fu A. Utility-basedanonymization using local recoding. In Proc. the 12th ACMSIGKDD Conf. Knowledge Discovery and Data Mining,Philadelphia, USA, August 2006, pp.785-790.

[26] Bayardo R J, Agrawal R. Data privacy through optimal k-anonymization. In Proc. Int. Conf. Data Engineering,Tokyo, Japan, April 2005, pp.217-228.

[27] Zheng Z, Kohavi R, Mason L. Real world performance of as-sociation rule algorithms. In Proc. the 7th ACM SIGKDDConf. Knowledge Discovery and Data Mining, San Francisco,USA, August 2001, pp.401-406.

[28] Xiao X, Tao Y. Anatomy: Simple and effective privacy preser-vation. In Proc. the 32nd Very Large Data Bases Conf.,Seoul, Korea, Sept. 2006, pp.139-150.
No related articles found!
Full text



No Suggested Reading articles found!

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved