k-匿名方法中相关视图集和准标识符的求解算法  

Algorithms to Find the Set of Relevant Views and Quasi-Identifiers for K-Anonymity Method

作　　者：宋金玲[1,2] 刘国华[1] 黄立明[2] 朱彩云[1] 

机构地区：[1]燕山大学计算机科学与工程系,河北秦皇岛066004 [2]河北科技师范学院计算机系,河北秦皇岛066004

出　　处：《计算机研究与发展》2009年第1期77-88,共12页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60773100);国家“十一五”科技支撑计划基金项目(2006BAK05B02)~~

摘　　要：准标识符是影响k-匿名方法有效性的关键因素.在视图发布过程中,求解准标识符所面临的问题是如何在已发布的视图集合中找出与待发布视图相关的全部视图.将已发布的视图集合与待发布的视图映射为一个超图,寻找相关视图集问题可被转化为在超图中求解特定结点间的全部通路问题.首先,给出了视图集向超图的映射方法及有关引理和定理,提出了基于超图的相关视图集求解算法;其次,研究了基本表中属性间不存在函数依赖和存在函数依赖两种情况下准标识符的组成结构,归纳出它们的特征,在此基础上,给出了基于相关视图集的准标识符求解算法.最后,对所提算法进行了正确性证明和时间复杂度分析.Quasi-identifier is a key factor to impact the validity of k-anonymity method. If the quasiidentifier is not identified correctly, the publishing view may still disclose secret information although it has been k-anonymized on the quasi-identifier. In the procedure of publishing views, an important problem concerning identifying quasi-identifiers is how to find all the views relevant to the publishing view from the set of published views. By mapping the set of published views and the publishing view into a hypergraph, the problem of finding the set of relevant views can be converted to searching for all the paths containing special edge between two given nodes in the hypergraph. In this paper, at first, the method mapping all the views to hypergraph and the related lemma and deciding theorems are presented; the algorithm for finding the set of relevant views based on hypergraph is proposed too. Secondly, the composing structures of the quasi-identifiers for the basic table with FDs and without FDs are studied respectively, and the characters of quasi-identifiers are generalized. Then, the algorithms to identify quasi-identifiers of the publishing view based on the set of relevant views for the cases with and without FDs are proposed. At last, the correctness of all the algorithms are proved, and the time complexity of these algorithms are analyzed. The algorithms finding the set of relevant views and quasi-identifiers can ensure the successful application of the k-anonymity method.

关 键 词：视图发布 信息泄露 K-匿名 准标识符 相关视图集 超图 

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