Title: Approximation algorithm for k-anonymity
| Speaker: | Tony Hu |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: The concept of k-anonymity was first described by Sweeney in 2002 as a method of providing data privacy when information is released to the public. Even after removing attributes such as ID numbers from a data set, often there is a set of attributes, called quasi-identifying attributes, that can be used to re-identify individuals within a data set. Thus, we impose the condition of k-anonymity, where require each row in a table to appear identical to k - 1 other row with respect to these quasi-identifying attributes; we do this by suppressing certain cells in the table. Naturally, we would like to minimize information loss as a result of imposing this condition, but this optimization problem is known to be NP-hard. Nonetheless, there exist algorithms that can efficiently find near-optimal solutions, and in particular we describe an O(log k)-approximation algorithm first published by Park and Shim in 2007.