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

We thank the reviewer for the detailed and constructive feedback. Below we address the specific concerns.

Runtime in experiments:

We thank the reviewer for raising this important point. We conducted additional experiments comparing our method with the most recent heuristic algorithm proposed in [ZWL+18]. We note that this algorithm performs on real-world data, but also has high computational complexity.The core idea of this algorithm involves:

1. Iteratively selecting a new cluster center as the point with the highest average distance from existing centers, and
2. Assigning the $k - 1$ nearest neighbors of that point to the same cluster.

This strategy, while intuitive, results in at least $\Omega(n^2)$ time complexity, even when we disregard other parameters such as $d$ and $k$.

To empirically assess runtime performance, we conducted experiments comparing the following algorithms:

• Mondrian: We used the publicly available Python implementation (referenced on page 12 of [EEMM24]).

• Our algorithm: Implemented in C++ for efficiency.

• [ZWL+18]: Since no official implementation was available, we implemented the algorithm ourselves in C++. We applied the same optimization strategies as in our own implementation, including multi-threading where applicable and pre-processing steps to speed up pairwise distance computations.

The experimental results confirm our theoretical expectations. On the Adult dataset with $k = 10$:

• Mondrian completed in approximately 1 second,
• Our algorithm completed in 3.78 seconds, and
• [ZWL+18] completed in 689.15 seconds (here the run time increases a lot as $k$ decreases, see the below table for details).

Moreover, motivated by the performance bottleneck of [ZWL+18], we investigated whether the core heuristic could be accelerated using ideas from our own algorithm. We found that substantial speed-ups are indeed possible, with minimal impact on performance.

In particular, we introduce the following modifications:

1. For the center selection step (Step 1), instead of computing the average distance for all points, we randomly sample a fixed number of candidate points.

2. Once a new center is chosen, we leverage Locality-Sensitive Hashing (LSH) to efficiently compute its approximate $k$-nearest neighbors. This process is similar to Lemmas 3.5 and 3.6 in our submission.

In our experiments, these modifications lead to a substantial reduction in runtime while preserving performance comparable to the original heuristic. Notably, the improved variant consistently outperforms the results presented in Section 5 of our current submission.

Below, we report the experimental results. We refer to the improved version of our new algorithm as Ours (Heuristic):

In summary, our algorithm achieves nearly-linear runtime in theory. Empirically, we also demonstrate that our algorithmic ideas can be adapted to existing heuristic methods, leading to significant speed-ups while preserving comparable performance.

Code: As the rebuttal policy does not allow uploading supplementary material or external links, we will release our code publicly with the next version of the paper.

We thank the reviewer for the detailed and constructive feedback. Below we address the specific questions.

Space complexity:

We thank the reviewer for pointing this out. We will include a more detailed space complexity analysis in the next version of the paper. It is correct that the use of LSH introduces additional space overhead. However, we note that in our algorithm, LSH is always computed over a subset of size $|J'| = (n \log n) / k$ (though multiple times), rather than over the entire dataset. As a result, the overall space complexity of our algorithm is:

In comparison, the algorithm in [AFK+05] does not provide an explicit space complexity discussion, but to the best of our knowledge, its space usage is $O(nd)$.

In Theorem 1.2, the total space complexity does not depend on $\epsilon$, as $\epsilon$ serves as a trade-off parameter between accuracy and parallel runtime.

Technical contributions:

• We present a reduction showing that achieving an $O(k)$-approximation for $k$-anonymity can be reduced to solving the minimum-size constrained clustering problem with an $O(1)$ pointwise approximation guarantee under squared $\ell_2$ distance . To our knowledge, this reduction is new to the literature.

• Our algorithm for solving the minimum-size constrained clustering problem is inspired by [EMMZ22], where locality-sensitive hashing (LSH) is used. However, as noted in lines 179–184, directly adapting their algorithm leads to a runtime of $n^{1 + 1/C^2 + o(1)} k$, which can be as large as $n^2$ when $k = \Theta(n)$. To overcome this, we incorporate a random sampling strategy that reduces $k$-nearest neighbor computations to 1-nearest neighbor computations, which to our knowledge, is generic and could have independent applications.

• Finally, we provide a lower bound result for single-point $k$-anonymity (a local version of the original problem), showing that computing an $o(k)$-approximation is hard. Extending this result to a reduction from the global version remains an open and interesting direction for future work.

Runtime in experiments:

We thank the reviewer for raising this important point. We conducted additional experiments comparing our method with the most recent heuristic algorithm proposed in [ZWL+18]. We note that this algorithm performs on real-world data, but also has high computational complexity.The core idea of this algorithm involves:

1. Iteratively selecting a new cluster center as the point with the highest average distance from existing centers, and
2. Assigning the $k - 1$ nearest neighbors of that point to the same cluster.

This strategy, while intuitive, results in at least $\Omega(n^2)$ time complexity, even when we disregard other parameters such as $d$ and $k$.

To empirically assess runtime performance, we conducted experiments comparing the following algorithms:

• Mondrian: We used the publicly available Python implementation (referenced on page 12 of [EEMM24]).

• Our algorithm: Implemented in C++ for efficiency.

• [ZWL+18]: Since no official implementation was available, we implemented the algorithm ourselves in C++. We applied the same optimization strategies as in our own implementation, including multi-threading where applicable and pre-processing steps to speed up pairwise distance computations.

The experimental results confirm our theoretical expectations. On the Adult dataset with $k = 10$:

• Mondrian completed in approximately 1 second,
• Our algorithm completed in 3.78 seconds, and
• [ZWL+18] completed in 689.15 seconds (here the run time increases a lot as $k$ decreases, see the below table for details).

Moreover, motivated by the performance bottleneck of [ZWL+18], we investigated whether the core heuristic could be accelerated using ideas from our own algorithm. We found that substantial speed-ups are indeed possible, with minimal impact on performance.

In particular, we introduce the following modifications:

1. For the center selection step (Step 1), instead of computing the average distance for all points, we randomly sample a fixed number of candidate points.

2. Once a new center is chosen, we leverage Locality-Sensitive Hashing (LSH) to efficiently compute its approximate $k$-nearest neighbors. This process is similar to Lemmas 3.5 and 3.6 in our submission.

In our experiments, these modifications lead to a substantial reduction in runtime while preserving performance comparable to the original heuristic. Notably, the improved variant consistently outperforms the results presented in Section 5 of our current submission.

Below, we report the experimental results. We refer to the improved version of our new algorithm as Ours (Heuristic):

In summary, our algorithm achieves nearly-linear runtime in theory. Empirically, we also demonstrate that our algorithmic ideas can be adapted to existing heuristic methods, leading to significant speed-ups while preserving comparable performance.

We thank the reviewer for the detailed and constructive feedback. Below we address the specific questions.

Motivation for k-anonymity:

We appreciate the question regarding our motivation for using k-anonymity over differential privacy (DP), and we will provide additional explanation in the revised version of the manuscript.

In [EEMM 24], the authors formally prove the following:

Let $\mathcal{M}$ be an arbitrary mechanism that satisfies $\epsilon$-edge differential privacy. Then, in order to achieve $E[J(\mathcal{M}(G), G)] \ge \alpha$, it must hold that $\epsilon = \Omega(\log (\alpha^2 n m))$, where $J(\cdot, \cdot)$ denotes the Jaccard similarity.

This result suggests that achieving high utility (i.e., preserving the structure of the original graph) under differential privacy requires a large value of $\epsilon$. However, when $\epsilon$ is large, the algorithm likely maintains the graph G unmodified thus exposing users to re-identification risks. Recall that the guarantee provided by $\epsilon$-DP is: $\Pr[\mathcal{M}(G) \in A] \le e^{\epsilon} \Pr[\mathcal{M}(G') \in A],$ which becomes nearly vacuous for large $\epsilon$.

In contrast, k-anonymity offers a different privacy-utility tradeoff. Prior work shows that if the optimal anonymized graph $E_{opt}$ satisfies $J(E, E_{opt}) \ge 1 - O(1/\log k)$, then efficient algorithms can find solutions with comparable utility. Furthermore, in the case of smooth k-anonymity, where edge additions and deletions are allowed, the required assumption can be relaxed to $J(E, E_{opt}) \ge O(1)$.

In recent years, several notable works on data anonymity have been published at top machine learning venues. Examples include:

• Hossein Esfandiari et al., Anonymous Bandits for Multi-User Systems (NeurIPS, 2022)
• Alessandro Epasto et al., Smooth Anonymity for Sparse Graphs (WWW, 2024)
• Xinyi Zheng et al., Building K-Anonymous User Cohorts with Consecutive Consistent Weighted Sampling (CCWS) (SIGIR, 2023)
• Krzysztof Choromanski et al., Adaptive Anonymity via b-Matching (NeurIPS, 2013)

These works highlight interest in anonymity and privacy-preserving algorithms in machine learning and other communities. Beyond foundational and algorithmic work, we observed $k$-anonymity has also been applied in several domains recently. Examples include:

• Edvinas Kruminis et al., BB-FLoC: A Blockchain-based Targeted Advertisement Scheme with K-Anonymity (Distributed Ledger Technologies: Research and Practice, 2024)
• Zhaowei Hu et al., KAIM: A distributed K-anonymity selection mechanism based on dual incentives (Ad Hoc Networks Journal. 2025)
• Stylianos Karagiannis et al., Mastering data privacy: leveraging K-anonymity for robust health data sharing (International Journal of Information Security, 2024)

Constant factors:

We agree with the reviewer that our theoretical bounds include several constant factors. However, our goal in this work is not to optimize these constants. Specifically:

• In Lemma 3.1, a factor of 8 appears;
• In the clustering step, the use of the triangle inequality introduces a factor of 2;
• Finally, the LSH-based algorithm introduces an additional constant $c_u$.

Johnson-Lindenstrauss (JL) target dimension:

Here we need to preserve all pairwise distances within a $(1 \pm 0.1)$ multiplicative error, a JL projection to $O(\log n)$ dimensions suffices.

More Experiments:

Motivated by the reviewers’ feedback, we conducted additional experiments comparing our method with the most recent heuristic algorithm proposed in [ZWL+18]. We note that this algorithm performs on real-world data, but also has high computational complexity. The core idea of this algorithm involves:

1. Iteratively selecting a new cluster center as the point with the highest average distance from existing centers, and
2. Assigning the $k - 1$ nearest neighbors of that point to the same cluster.

This strategy, while intuitive, results in at least $\Omega(n^2)$ time complexity, even when we disregard other parameters such as $d$ and $k$.

To empirically assess runtime performance, we conducted experiments comparing the following algorithms:

• Mondrian: We used the publicly available Python implementation (referenced on page 12 of [EEMM24]).

• Our algorithm: Implemented in C++ for efficiency.

• [ZWL+18]: Since no official implementation was available, we implemented the algorithm ourselves in C++. We applied the same optimization strategies as in our own implementation, including multi-threading where applicable and pre-processing steps to speed up pairwise distance computations.

The experimental results confirm our theoretical expectations. On the Adult dataset with $k = 10$:

• Mondrian completed in approximately 1 second,
• Our algorithm completed in 3.78 seconds, and
• [ZWL+18] completed in 689.15 seconds (here the run time increases a lot as $k$ decreases, see the below table for details).

Moreover, motivated by the performance bottleneck of [ZWL+18], we investigated whether the core heuristic could be accelerated using ideas from our own algorithm. We found that substantial speed-ups are indeed possible, with minimal impact on performance.

In particular, we introduce the following modifications:

1. For the center selection step (Step 1), instead of computing the average distance for all points, we randomly sample a fixed number of candidate points.

2. Once a new center is chosen, we leverage Locality-Sensitive Hashing (LSH) to efficiently compute its approximate $k$-nearest neighbors. This process is similar to Lemmas 3.5 and 3.6 in our submission.

In our experiments, these modifications lead to a substantial reduction in runtime while preserving performance comparable to the original heuristic. Notably, the improved variant consistently outperforms the results presented in Section 5 of our current submission.

Below, we report the experimental results. We refer to the improved version of our new algorithm as Ours (Heuristic):

In summary, our algorithm achieves nearly-linear runtime in theory. Empirically, we also demonstrate that our algorithmic ideas can be adapted to existing heuristic methods, leading to significant speed-ups while preserving comparable performance.

The authors gave a satisfactory rebuttal, and I uphold my positive rating of this paper. I believe the paper has to be considered on it's own merits as the solution to a scientific problem (regardless of whether k-anonymity is a old or new method). The proof and algorithmic techniques are still of value. Improvements to the understanding of a classic method like linear regression for instance, still hold merit and further scientific understanding in the current day, for instance.

We thank the reviewer for the detailed and constructive feedback. Below we address the specific concerns.

Motivation for k-anonymity:

We appreciate the question regarding our motivation for using k-anonymity over differential privacy (DP), and we will provide additional explanation in the revised version of the manuscript.

In [EEMM 24], the authors formally prove the following:

Let $\mathcal{M}$ be an arbitrary mechanism that satisfies $\epsilon$-edge differential privacy. Then, in order to achieve $E[J(\mathcal{M}(G), G)] \ge \alpha$, it must hold that $\epsilon = \Omega(\log (\alpha^2 n m))$, where $J(\cdot, \cdot)$ denotes the Jaccard similarity.

This result suggests that achieving high utility (i.e., preserving the structure of the original graph) under differential privacy requires a large value of $\epsilon$. However, when $\epsilon$ is large, the algorithm likely maintains the graph G unmodified thus exposing users to re-identification risks. Recall that the guarantee provided by $\epsilon$-DP is: $\Pr[\mathcal{M}(G) \in A] \le e^{\epsilon} \Pr[\mathcal{M}(G') \in A],$ which becomes nearly vacuous for large $\epsilon$.

In contrast, k-anonymity offers a different privacy-utility tradeoff. Prior work shows that if the optimal anonymized graph $E_{opt}$ satisfies $J(E, E_{opt}) \ge 1 - O(1/\log k)$, then efficient algorithms can find solutions with comparable utility. Furthermore, in the case of smooth k-anonymity, where edge additions and deletions are allowed, the required assumption can be relaxed to $J(E, E_{opt}) \ge O(1)$.

In recent years, several notable works on data anonymity have been published at top machine learning venues. Examples include:

• Hossein Esfandiari et al., Anonymous Bandits for Multi-User Systems (NeurIPS, 2022)
• Alessandro Epasto et al., Smooth Anonymity for Sparse Graphs (WWW, 2024)
• Xinyi Zheng et al., Building K-Anonymous User Cohorts with Consecutive Consistent Weighted Sampling (CCWS) (SIGIR, 2023)
• Krzysztof Choromanski et al., Adaptive Anonymity via b-Matching (NeurIPS, 2013)

These works highlight interest in anonymity and privacy-preserving algorithms in machine learning and other communities. Beyond foundational and algorithmic work, we observed $k$-anonymity has also been applied in several domains recently. Examples include:

• Edvinas Kruminis et al., BB-FLoC: A Blockchain-based Targeted Advertisement Scheme with K-Anonymity (Distributed Ledger Technologies: Research and Practice, 2024)
• Zhaowei Hu et al., KAIM: A distributed K-anonymity selection mechanism based on dual incentives (Ad Hoc Networks Journal. 2025)
• Stylianos Karagiannis et al., Mastering data privacy: leveraging K-anonymity for robust health data sharing (International Journal of Information Security, 2024)

Runtime in experiments:

We thank the reviewer for raising this important point. We note that the algorithms we mention indeed have a slow runtime on real-world data. For instance, the most recent heuristic algorithm proposed in [ZWL+18] exhibits high computational complexity. The core idea of this algorithm involves:

1. Iteratively selecting a new cluster center as the point with the highest average distance from existing centers, and
2. Assigning the $k - 1$ nearest neighbors of that point to the same cluster.

This strategy, while intuitive, results in at least $\Omega(n^2)$ time complexity, even when we disregard other parameters such as $d$ and $k$.

To empirically assess runtime performance, we conducted experiments comparing the following algorithms:

• Mondrian: We used the publicly available Python implementation (referenced on page 12 of [EEMM24]).

• Our algorithm: Implemented in C++ for efficiency.

• [ZWL+18]: Since no official implementation was available, we implemented the algorithm ourselves in C++. We applied the same optimization strategies as in our own implementation, including multi-threading where applicable and pre-processing steps to speed up pairwise distance computations.

The experimental results confirm our theoretical expectations. On the Adult dataset with $k = 10$:

• Mondrian completed in approximately 1 second,
• Our algorithm completed in 3.78 seconds, and
• [ZWL+18] completed in 689.15 seconds (here the run time increases a lot as $k$ decreases, see the below table for details).

Moreover, motivated by the performance bottleneck of [ZWL+18], we investigated whether the core heuristic could be accelerated using ideas from our own algorithm. We found that substantial speed-ups are indeed possible, with minimal impact on performance.

In particular, we introduce the following modifications:

1. For the center selection step (Step 1), instead of computing the average distance for all points, we randomly sample a fixed number of candidate points.

2. Once a new center is chosen, we leverage Locality-Sensitive Hashing (LSH) to efficiently compute its approximate $k$-nearest neighbors. This process is similar to Lemmas 3.5 and 3.6 in our submission.

In our experiments, these modifications lead to a substantial reduction in runtime while preserving performance comparable to the original heuristic. Notably, the improved variant consistently outperforms the results presented in Section 5 of our current submission.

Below, we report the experimental results. We refer to the improved version of our new algorithm as Ours (Heuristic):

In summary, our algorithm achieves nearly-linear runtime in theory. Empirically, we also demonstrate that our algorithmic ideas can be adapted to existing heuristic methods, leading to significant speed-ups while preserving comparable performance.