Nearly-Linear Time and Massively Parallel Algorithms for $k$-anonymity

k-anonymity is a widely-used privacy-preserving concept that ensures each record in a dataset is indistinguishable from at least k -1 other records. We revisit k-anonymity by suppression and give an O(k)-approximation algorithm with a nearly-linear runtime of O(nd + n • (n/k) 1/C 2 +o( 1) ) for any constant C, where n is the number of records and d is the number of attributes. Previous algorithms with provable guarantees either (1) achieve the same O(k) approximation ratio but require at least O(n 2 k) runtime, or (2) provide a better O(log k) approximation ratio at the cost of an impractical O(n 2k ) worst-case runtime for general d and k. Our algorithm extends to the Massively Parallel Computation (MPC) model, where it gives an MPC algorithm requiring O(log 1+ε n) rounds and total space O(n 1+γ (d + k)). Empirically, we also demonstrate that our algorithmic ideas can be adapted to existing heuristic methods, leading to significant speed-ups while preserving comparable performance. On the hardness side, we study the related single-point k-anonymity problem, where the goal is to select k -1 additional records to make a given record indistinguishable. Assuming the dense vs random conjecture in complexity theory, we show that for n = k c , no algorithm can achieve a k 1-O(1/c) approximation in poly(n) time, providing evidence for the inherent hardness of the k-anonymity problem.

† Part of the work was done while Honghao Lin was a student researcher in Google Research.

k-anonymity reduces the risk of re-identification while preserving data utility for analysis. An example can be found in Table 1. In this paper, we will only consider the case of suppression where each entry of every attribute is either included in the output, or replaced with the '⋆' character. Most research on k-anonymity has focused on finding the optimal (or near-optimal) k-anonymous dataset. That is, the one that minimizes the number of hidden attributes and thereby best preserves the original data. The work of [MW04] demonstrated that finding the optimal solution is NP-hard but provided an O(k log k)-approximation algorithm with a runtime exponential in k. Later, [AFK + 05] improved this to an O(k)-approximation with a runtime of O(n 2 k). Subsequently, [PS07, KT12] further enhanced the approximation to O(log k), though their algorithm has a worst-case runtime of O(n 2k ). In addition to algorithms with provable guarantees, other studies have proposed heuristics for various anonymization approaches. For example [LDR06] introduced a heuristic algorithm for k-anonymization of quasi-identifiers, utilizing a construction similar to k-d trees, [DXTK15] by freeform generalization and [BKBL07, ZWL + 18] proposed heuristics based on clustering. Age Marital status Home country Gender 20∼29 Single USA Male 30∼39 Divorce China Female 20∼29 Single USA Female 30∼39 Separation Korea Female Age Marital status Home country Gender 20∼29