Problem of Finding the Optimal Value on Quasi-Identifier for k-Anonymity Model
LI Fangling · Jisuanji kexue yu tansuo · 2010
The value on quasi-identifier is a key factor to impact the degree of privacy protection and data quality of k-anonymous tables.After generalization trees of quasi-identifier attributes have been generated,how to find the optimal value on quasi-identifier is very important for anonymous table to meet the privacy protection requirements and achieve the highest data quality.To solve this,firstly,the problem of finding the optimal value on quasi-identifier is proved to be a NP-complete problem.Secondly,the approximate method of finding the optimal value on quasi-identifier is presented,and the approximate algorithm for finding the optimal value on quasi-identifier is pro-posed.Lastly,the correctness of the algorithm is proved and the time complexity of the algorithm is analyzed.