Efficient near-optimal t-closeness with low information loss

Abstract

The t-closeness technique is one of the most popular techniques for preserving individual privacy in data. It involves generalizing and suppressing some attributes of a given table, after partitioning the set of all records of that table into equivalence classes that satisfy a certain constraint. We present a new method to partition the set of records of a table into such equivalence classes. Our method has several advantages over the existing methods for this task. Firstly, the classes generated by our method are nearoptimal, in that they satisfy the t-closeness constraint for even the “smallest” t value for which t-closeness is achievable and useful for the given table, thereby providing the highest amount of privacy. Secondly, our method generates classes of approximately the same size, resulting in low information loss caused by generalization of attribute values. Lastly, while generating classes with minimum information loss is known to be NP-hard, our classes with reasonably low information loss can be generated in just polynomial time.