Deriving Private Information from Randomized Dataset using Data Reorganization Techniques

Abstract

Publishing data about individuals without revealing
sensitive information about them is an important problem. To enforce privacy-preserving paradigms, such as k-anonymity and l-diversity, while minimizing the information loss incurred in the anonymizing process (i.e. maximize data utility). work well for fixed-schema data,
with low dimensionality. Nevertheless, certain applications require privacy-preserving publishing of transaction data (or basket data), which involves hundreds or even thousands of dimensions, rendering
existing methods unusable. A novel anonymization method for sparse high dimensional data is achieved. Two categories of novel anonymization method for sparse high-dimensional data. The first category is based on approximate nearest-neighbor (NN) search in high-dimensional spaces, which is efficiently performed through
locality-sensitive hashing (LSH). In the second category, a data transformation that capture the correlation in the underlying data Gray encoding-based sorting. These representations facilitate the formation of anonymized groups with low information loss, through
an efficient linear-time heuristic.