Adaptive Anonymization of Data with b-Edge Covers

Authors: Arif Khan (Pacific Northwest National Laboratory), Krzysztof Choromanski (Google LLC), Alex Pothen (Purdue University), S M Ferdous (Purdue University), Mahantesh Halappanavar (Pacific Northwest National Laboratory), Antonino Tumeo (Pacific Northwest National Laboratory)

Abstract: We explore the problem of sharing data that pertains to individuals with anonymity guarantees, where each user requires a desired level of privacy. We propose the first shared-memory as well as distributed memory parallel algorithms for the adaptive anonymity problem that achieves this goal, and produces high quality anonymized datasets.

The new algorithm is based on an optimization procedure that iteratively computes weights on the edges of a dissimilarity matrix, and at each iteration computes a minimum weighted b-Edge cover in the graph. We are able to solve adaptive anonymity problems with hundreds of thousands of instances and hundreds of features on a leadership-class supercomputer in under five minutes. Our algorithm scales up to 4K cores on a distributed memory supercomputer, while also providing good speedups on shared memory multiprocessors. On smaller problems, where an algorithm based on Belief Propagation is feasible, our algorithm is two orders of magnitude faster.




Back to Technical Papers Archive Listing