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

doi:10.3778/j.issn.1673-9418.2010.11.006

计算机科学与探索 ›› 2010, Vol. 4 ›› Issue (11): 1010-1018.DOI: 10.3778/j.issn.1673-9418.2010.11.006

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

王丹丽¹⁺, 刘国华^1,2,3, 宋金玲^1,4, 李芳玲⁵

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

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-11-01 发布日期:2010-11-01
通讯作者: 王丹丽

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

WANG Danli¹⁺, LIU Guohua^1,2,3, SONG Jinling^1,4, LI Fangling⁵

1. Department of Computer Science and Engineering, School of Information Science and Engineering, Yanshan University, Qinhuangdao, Hebei 066004, China
2. College of Computer Science and Technology, Donghua University, Shanghai 201620, China
3. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China
4. Department of Computer, Hebei Normal University of Science & Technology, Qinhuangdao, Hebei 066004, China
5. Department of Information Technology, Shandong Polytechnic Vocational College, Jining, Shandong 272017, China

Received:1900-01-01 Revised:1900-01-01 Online:2010-11-01 Published:2010-11-01
Contact: WANG Danli

摘要/Abstract

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

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

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

中图分类号:

TP309.2

王丹丽1+ , 刘国华1,2,3 , 宋金玲1,4 , 李芳玲5 . k-匿名模型中准标识符最佳值的求解问题*[J]. 计算机科学与探索, 2010, 4(11): 1010-1018.

WANG Danli¹⁺, LIU Guohua^1,2,3, SONG Jinling^1,4, LI Fangling⁵. Problem of Finding the Optimal Value on Quasi-Identifier for k-Anonymity Model*[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4(11): 1010-1018.

[1]	包盼盼，陶传奇，黄志球. 面向开源源码大数据的数据质量研究[J]. 计算机科学与探索, 2020, 14(3): 389-400.
[2]	董祥祥，高昂，梁英，毕晓迪. 动态社会网络数据发布隐私保护方法[J]. 计算机科学与探索, 2019, 13(9): 1441-1458.
[3]	李文，黄丽韶，罗恩韬. 移动医疗中个性化l-多样性匿名隐私保护模型[J]. 计算机科学与探索, 2018, 12(5): 761-768.
[4]	韩超，段磊，邓松，王慧锋，唐常杰. 基于Spark的序列数据质量评价[J]. 计算机科学与探索, 2017, 11(6): 897-907.
[5]	张安珍，门雪莹，王宏志，李建中，高宏. 大数据上基于Hadoop的不一致数据检测与修复算法[J]. 计算机科学与探索, 2015, 9(9): 1044-1055.
[6]	王慧锋，段磊，胡斌，邓松，王文韬，秦攀. 带间隔约束的序列数据质量评价算法设计[J]. 计算机科学与探索, 2015, 9(10): 1180-1194.
[7]	许道云，王晓峰. 一个正则NP-完全问题及其不可近似性[J]. 计算机科学与探索, 2013, 7(8): 691-697.
[8]	辛婷婷, 刘国华. K-匿名隐私保护模型下的Top-k查询[J]. 计算机科学与探索, 2011, 5(8): 751-759.
[9]	何贤芒, 陈华辉, 肖仰华, 汪卫, 施伯乐. 动态数值敏感属性的数据隐私保护[J]. 计算机科学与探索, 2011, 5(8): 740-750.
[10]	孟啸+，王宏志，高宏，李建中. bibEOS：一个高质量的社会化文献检索与管理系统[J]. 计算机科学与探索, 2010, 4(1): 54-63.
[11]	潘晓+,肖珍,孟小峰. 位置隐私研究综述[J]. 计算机科学与探索, 2007, 1(3): 268-281.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics