k-匿名模型中准标识符最佳值的求解问题

作者：**丽; 刘国华; 宋金玲; 李芳玲

来源：计算机科学与探索, 2010, (11): 1010-1018.

• k-匿名
• 数据质量
• 泛化树
• 准标识符最佳值
• NP-完全 k-anonymity
• data quality
• generalization tree
• optimal value on quasi-identifier
• NP-complete

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

• 出版日期2010
• 单位山东理工职业学院; 河北科技师范学院; 燕山大学; 计算机软件新技术国家重点实验室; 东华大学; 南京大学