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

Problem of Finding the Optimal Value on Quasi-Identifier for k-Anonymity Model

作　　者：王丹丽[1] 刘国华[1,2,3] 宋金玲[1,4] 李芳玲[5] 

机构地区：[1]燕山大学信息科学与工程学院计算机科学与工程系,河北秦皇岛066004 [2]东华大学计算机科学与技术学院,上海201620 [3]南京大学计算机软件新技术国家重点实验室,南京210093 [4]河北科技师范学院计算机系,河北秦皇岛066004 [5]山东理工职业学院信息工程系,山东济宁272017

出　　处：《计算机科学与探索》2010年第11期1010-1018,共9页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.60773100~~

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

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

分 类 号：TP309.2[自动化与计算机技术—计算机系统结构]