Subspace Partitioning Based Dynamic Programming Algorithm for Optimal k-anonymization
Shangbin Liao · Journal of Chinese Computer Systems · 2011
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.