隐私保护关系型数据发布的多维划分动态规划算法*

南京大学学报(自然科学版) ›› 2013, Vol. 49 ›› Issue (2): 258–267.

隐私保护关系型数据发布的多维划分动态规划算法*

王一蕾**，吴英杰，孙岚

出版日期:2015-10-21 发布日期:2015-10-21
作者简介: (福州大学数学与计算机科学学院，福州，350108)
基金资助:
福建省自然科学基金(2010J01330),福州大学科技发展基金(2010－X Y-18 , 2010－X Y-20）

A dynamic programming algorithm based on multidimensional
partitioning for privacy preserving relational data publishing

Wang Yi- Lei ,Wu Ying一Jie，Sun Lan

Online:2015-10-21 Published:2015-10-21
About author: (College of Mathematics and Computer Science,Fuzhou University,Fuzhou，350108 , China)

摘要/Abstract

摘要： 目前大部分隐私保护关系型数据发布算法均未能有效兼顾算法效率和发布数据的可用性.从
空间多维划分的角度研究关系型数据发布中的隐私保护问题，发现前期研究提出的基于子空间划分的
隐私保护最优k-匿名动态规划算法(k-ASPDP)可适用于多种隐私保护机制，进而设计出一种基于多维
划分的隐私保护关系型数据发布动态规划算法框架Bottom-Up MG，并针对动态规划算法k-ASPDP空
间复杂度较大的不足，提出一个空间可扩展性强的混合k-名化算法k-ASPDP+实验分别对以1-多样
胜为隐私保护机制的Bottom-Up MG算法和k-ASPDP+算法所发布数据的可用性及算法效率与同类
算法进行比较分析.实验结果表明，本文算法是有效可行的.

Abstract: Recently, privacy preserving data publishing has been a hot topic in data privacy preserving research
fields. The goal of privacy preserving data publishing is to propose safe and effective algorithms for data processing
before data rclcasing,while ensuring high utility of the released data. However,most of the previous works on priva-
cy preserving relational data publishing can not effectively take into account the algorithm efficiency and the availa-
bility of publishing data. In this paper,wc revisit privacy preserving relational data publishing from the perspective of
space multidimensional partitioning. It is found that subspace partitioning based dynamic programming algorithm k-
ASPDP designed in our previous work for optimal k-anonymization can be applied to multiple privacy preserving
mechanisms. Based on this,a dynamic programming algorithm framework Bottom-Up MU based on multidimensional
partitioning for privacy preserving relational data publishing is presented in this paper. After that, in order to ovet-
come the deficiency of high space complexity of the dynamic programming algorithm k-ASPDP,we propose a hybrid
k-anonymous algorithm k-ASPDP+ with high spatial scalability. Experimental analysis arc designed by comparing
Bottom-Up MU under 1-diversity privacy preserving mechanism as well as k-ASPDP+ and the traditional algorithm
on the released data availability and the algorithm efficiency. Experimental results show that the proposed algorithms
in this paper are effective and feasible.

王一蕾**，吴英杰，孙岚
. 隐私保护关系型数据发布的多维划分动态规划算法*[J]. 南京大学学报(自然科学版), 2013, 49(2): 258–267.

Wang Yi- Lei ,Wu Ying一Jie，Sun Lan
. A dynamic programming algorithm based on multidimensional
partitioning for privacy preserving relational data publishing
[J]. Journal of Nanjing University(Natural Sciences), 2013, 49(2): 258–267.

参考文献

[1]Samarati P. Protecting respondent’s identities in mi- crodata release. IEEE Zi-ansactions on Knowledge
and Data Engineering,2001，13(6):1010一1027.
[2]Sweeney L. K-anonymity; A model for protecting privacy. international Journal on Uncertainty,
Fuzziness and Knowledge-based Systems, 2002，10(5):557一570.
[3]Meyerson A，Williams R. On the complexity of optimal k-anonymity. Proceedings of the 23^rd
ACM SIGMOD Symposium on Principles of Da- tabase Systems. New York:ACM Press，2004: 223一228.
[4]LeFevre K，DeWitt D J，Ramakrishnan R, lncog nito:Efficient full-domain k一anonymity. Proceed
ings of the 24^th ACM SIGMOD International Conference on Management of Data. New York:ACM Press,2005:49~60
[5]Park H,Shim K. Approximate algorithms for k-ano- nymity. Proceedings of the 26^th ACM SIGMOD In-
ternational Conference on Manage-ment of Data. New York:ACM Press,2007:67一78.
[6]Zhou S G,Li F,Tao Y F,et al. Privacy preserva- tion in database applications:A survey. Chinese
Journal of Computers, 2009，32(5):847一861. (周水庚，李丰，陶宇飞等.面向数据库应用的
隐私保护研究综述.计算机学报，2009,32(5); 847一861).
[7]Iyengar V.Transforming data to satisfy privacy constraints. Proceedings of the 8th ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining. New York; ACM Press, 2002: 279一288.
[8]Bayardo R，Agrawal R. Data privacy through op-timal k-anonymization. Proceedings of the 21^st
IEEE International Conference on Data Engineer- ing. Piscataway;lEEE Press,2005:217~228.
[9]LeFevre K, De Witt D J，Ramakrishnan R. Mondrian multidimensional k- anonymity. Proceedings of the
22nd IEEE International Conference on Data Engi- neering. Piscataway; IEEE Press, 2006 ; 25.
[10]Xu J,Wang W,Pei J,et al. Utility-based anonymiza- tion using local recoding. Proceedings of the 12^th
ACM SIGKDD International Conference on Knowl- edge Discovery and Data Mining. New York; ACM Press,2006:785一790.
[11]Hore B, Jammalamadaka R，Mehrotra S. Flexible anonymization for privacy preserving data pub-
lishing; A systematic search based approach. Pro- ceedings of the 2007 SIAM international Confer-
ence on Data Mining. Philadelphia; SIAM Press，2007:497一502.
[12]Wu Y J,Wang Y L,Tang Q M,et al. A subspace partitioning based dynamic programming algo-
rithm for optimal k-anonymization. Journal of Chinese Computer Systems,2011，32(10);2002一
2007.(吴英杰，土一蕾，唐庆明等.一种基于子空间划分的最优k一匿名动态规划算法.小型微型计算机系统，2011,32(10);2002-2007).
[13]Asuncion A, Newman D J. UCI Machine Learning Re- pository, http;//mlearn, ics. uci. edu/MLRepository. html , 2007.
[14]Ghinita G,Zao Y,Kalnis P. On the anonymization of sparse higlrdimensional data. Proceedings of the 24^th
IEEE international Conference on Data Engineering. Piscataway;IEEE Press,2008;715一724.
[15]Ghinita G,Kalnis P, Tao Y. Anonymous publication of sensitive transactional data. IEEE Transactions on
Knowledge and Data Engineering, 2011，23(2): 161~174.
[16]Gao Y. Progress of data mining in China. Journal of Nanjing University C Natural Sciences) , 2011 ,47(4):
351 -353.(高阳.中国数据挖掘研究进展.南京大学学报(自然科学),2011,47(4);351-353).

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed