一种基于子空间划分的最优k-匿名动态规划算法  

Subspace Partitioning Based Dynamic Programming Algorithm for Optimal k-anonymization

作　　者：吴英杰[1,2] 王一蕾[1] 唐庆明[1] 孙志挥[2] 廖尚斌[1] 

机构地区：[1]福州大学数学与计算机科学学院,福州350108 [2]东南大学计算机科学与工程学院,南京211189

出　　处：《小型微型计算机系统》2011年第10期2002-2007,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61003057)资助;福建省自然科学基金项目(2010J01330)资助

摘　　要：目前大部分k-匿名算法未能有效兼顾算法效率和发布数据的可用性.从子空间划分的角度研究基于空间多维划分的最优k-匿名问题,发现所有可能的子空间数量远小于所有可能的划分数量,并从理论上分析基于子空间划分的最优k-匿名问题具有最优子结构性质,从而设计出基于子空间划分的隐私保护最优k-匿名动态规划算法k-ASPDP.实验对算法k-ASPDP发布数据的可用性及算法效率与同类算法进行比较分析.实验结果表明,算法k-ASPDP是有效可行的.Recently,privacy preserving data publishing has been a hot topic in data privacy preserving research fields.Most of the previous works on k-anonymization can not effectively take into account the algorithm efficiency and the availability of publishing data.In this paper,we revisit the optimal k-anonymity based on multidimensional partitioning from the perspective of subspace division.It is found that all the possible subspace number is much less than all the possible number of multidimensional partitioning.Theoretical analysis proves that the optimal k-anonymization based on subspace division satisfies the nature of optimal substructure.After that,a dynamic programming algorithm k-ASPDP for optimal k-anonymization is proposed.Experimental analysis is designed by comparing k-ASPDP and the traditional algorithm on the released data availability and the algorithm efficiency.Experimental results show that k-ASPDP is effective and feasible.

关 键 词：隐私保护 最优k-匿名 算法 子空间划分 动态规划 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]