New algorithm with lower upper size bound for k-anonymity

k-Anonymity is a well-researched privacy principle for data publishing. It requires that each tuple of a public released table can not be identified with a probability higher than 1 over k. According to literatures, one way to achieve k-anonymity is to generalize the table into several anonymization groups. All tuples within a group is indistinguishable. However, best of our knowledge, the worst-case upper bound on size of anonymization groups resulting from existing algorithms is not good, and the lowest value is 2k - 1. This paper propose a new algorithm for k-anonymity focusing on improving the solution quality. We show that the upper bound of our algorithm is lower than 2k - 1 in non-trivial cases, and when n > k², the bound becomes k + 1. Experiments on real world dataset demonstrate our conclusions.