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

Quasi-identifier is a key factor to impact the validity of k-anonymity method. If the quasi-identifier 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.