Efficient algorithms for identifying privacy vulnerabilities

The automatic identification of privacy vulnerabilities in datasets is an important step in the privacy-preserving data publishing process, and an area of increased interest for commercial data masking products. In this paper, we propose two multi-threaded algorithms for discovering privacy vulnerabilities in datasets, in the form of combinations of attributes leading to few records. Our algorithms fully utilize the execution environment and outperform the state-of-the-art to the extent that we had to design a multi-threaded counterpart of the state-of-the-art method to form the baseline for our experiments. Through experimental evaluation on a large set of datasets, we show that our algorithms can analyze microdata consisting of millions of records in less than 10 minutes, when the baseline method required more than 3 hours.