Privacy-Preserving Clustering for Multi-dimensional Data Randomization Under LDP

Randomization of multi-dimensional data under local differential privacy is a significant and practical application of big data. Because of the dimensionality issues, most existing works suffer from low accuracy when estimating joint probability distributions. In this paper, a set of attributes is divided into smaller clusters where the attributes are associated in terms of their dependencies. A privacy-preserving algorithm is proposed to estimate the dependencies of an attribute without disclosing the private values in the multi-dimensional data. Local differential privacy is guaranteed in the scheme. Using the clusters of attributes, the joint probabilities for multi-dimensional data can be estimated efficiently using two building blocks, called RR-independent and RR-Ind-Joint schemes. The experiments using some open datasets demonstrate that the dependencies of attributes can be estimated accurately and that the proposed algorithm outperforms existing state-of-the-art schemes in cases where the dimensionality is high.