  The curse of dimensionality has remained a challenge for a wide variety of
algorithms in data mining, clustering, classification and privacy. Recently, it
was shown that an increasing dimensionality makes the data resistant to
effective privacy. The theoretical results seem to suggest that the
dimensionality curse is a fundamental barrier to privacy preservation. However,
in practice, we show that some of the common properties of real data can be
leveraged in order to greatly ameliorate the negative effects of the curse of
dimensionality. In real data sets, many dimensions contain high levels of
inter-attribute correlations. Such correlations enable the use of a process
known as vertical fragmentation in order to decompose the data into vertical
subsets of smaller dimensionality. An information-theoretic criterion of mutual
information is used in the vertical decomposition process. This allows the use
of an anonymization process, which is based on combining results from multiple
independent fragments. We present a general approach which can be applied to
the k-anonymity, l-diversity, and t-closeness models. In the presence of
inter-attribute correlations, such an approach continues to be much more robust
in higher dimensionality, without losing accuracy. We present experimental
results illustrating the effectiveness of the approach. This approach is
resilient enough to prevent identity, attribute, and membership disclosure
attack.
