Generating t-Closed Partitions of Datasets with Multiple Sensitive Attributes

Abstract

The popular t-closeness privacy model requires the "distance" between the distribution of sensitive attribute values in any given raw dataset and their distribution in every equivalence class created to not exceed some privacy threshold t. While most existing methods for achieving t-closeness handle data with just a single sensitive attribute, datasets with multiple sensitive attributes are very common in the real world. Here we demonstrate a technique for creating equivalence classes from a dataset containing multiple sensitive attributes. The equivalence classes generated by our method satisfy t-closeness without taking any $t$ values as input. While generalization of quasi-identifier attributes leads to information loss, the size of generated classes is roughly identical and differs by at most one, which results in a lower information loss. Generating classes with minimum information loss for a given value of $t$ is NP-hard, the equivalence classes generated by our method takes O(r log r) time.