Improving Strict Partition for Privacy Preserving Data Publishing

Publishing the original form of data, typically the kind of data which contains personal information, will violate individual privacy. One challenge problem is how to release privacy preserved data while it is still useful. This paper studies partition-based algorithms for privacy preserving data publishing. Such kind of algorithms sets total orders over each attribute domain of a given table, and maps each tuple into a multidimensional space. Then finding an anonymized form of the original data equals to finding a partition of a corresponding multidimensional rectangular box. If different regions does not intersect with each other, a partition is called a strict partition; Otherwise, it is a called a relaxed partition. This paper proves that the data quality and utility of a given strict partition can be improved by further partitioning it into smaller but intersecting subregions. Then, combining advanced relaxed partition technique and Strict Mondrian Algorithm(the state-of-the-art strict partition-based algorithm), we design a Hybrid Algorithm. Through experiments on the famous adult dataset, we show that the anonymized result of the Hybrid Algorithm is better than the solutions produced by Strict Mondrian and two advanced relaxed partition-based algorithms according to existing quality and utility evaluation metrics.