Optimal hierarchical partition for k-Anonymity
Qingming Tang, Yingjie Wu, Xiaodong Wang · 2010
K-Anonymity is a famous and widely used privacy principle for protecting private information. It requires that each tuple of a public released data table must be indistinguishable from at least other k - 1 tuples. Given a table, finding an optimal k-anonymous version is NP-hard in most previous recoding ”model”. Thus, designing an efficient algorithm to find high-quality k-anonymous version is still challenge, though k-anonymity is well-researched. In recent years, hierarchical partition is proposed and widely accepted. Viewing the given table as a multidimensional space, each hierarchical partition of the space is a multidimensional recoding under some special constraints. Previous works need huge computation to find optimal hierarchical partition, and efficient algorithms just find a reasonable hierarchical partition. In this paper, we show that optimal hierarchical partition for k-anonymity can be obtained within polynomial time when a fixed quasi-identifier is given. We then design a bottom-up algorithm using dynamic approach. Through theoretical analysis and experiments, we show that our algorithm finds better results than related works, and our algorithm runs significantly fast comparing with other optimal algorithms for hierarchical partition.