Deriving Private Information from Randomized Dataset Using Data Reorganization Techniques

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 is Gray encoding-based sorting. These representations facilitate the formation of anonymized groups with low information loss, through an efficient linear-time heuristic.