Abstract: 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.

Key words: k-anonymity, data quality, generalization tree, optimal value on quasi-identifier, NP-complete

摘要： 准标识符值是影响k-匿名表隐私保护程度和数据质量的关键因素。如何在给定各个准标识符属性泛化树的情况下求解准标识符最佳值, 对匿名表在满足隐私保护要求的同时达到最高的数据质量具有重要意义。针对这一问题, 证明了准标识符最佳值的求解问题是NP-完全问题, 提出了准标识符最佳值的近似求解方法, 并给出了准标识符最佳值的近似求解算法; 最后, 对算法进行了正确性证明和时间复杂度分析。

关键词: k-匿名, 数据质量, 泛化树, 准标识符最佳值, NP-完全