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

Subspace Partitioning Based Dynamic Programming Algorithm for Optimal k-anonymization

目前大部分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.