Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time

Summary

This paper studies dynamic algorithms for k-median (and k-means) in general metrics. The main result is an \tilde{O}(k) update time, poly(k) query time algorithm that achieves O(1)-approximation. Here, the update model is point insertion/deletion, and the algorithm has access to the distance oracle. A query operation asks to return a list of k points that is O(1)-approximate. The result improves over the k^2 update time achieved in HK20. This is achieved using a somewhat different but more direct approach. In particular, in HK20, a general reduction to coreset via merge-and-reduce framework was employed, but this work employs a direct dynamization of MP04. Comprehensive experiments are also provided. Compared with HK20 as a baseline, the new algorithm runs faster and achieves an overall better accuracy.

Strengths

- The paper achieves near-linear in k update time, which is a nice improvement over the previous k^2 - The experiments are convincing, and justify the theoretical improvement - A nearly-matching lower bound is provided

Weaknesses

- This work only yields O(1)-approx, while HK20 uses coreset approach and hence can build an eps-coreset even for general metrics (even though it does not imply an efficient algorithm for finding a solution). This also means this work cannot be easily generalized to the Euclidean case, where near-linear time PTAS was known. - The query time is k^2, which may be improved

Questions

- The first paragraph of "our techniques" tried to explain why HK20 has k^2 dependence, but it's not very clear. Here, the black-box coreset is linear in k, and the depth of the binary tree is O(log n). Then how come we have another k factor? - Followup of the above question: is it true that HK20 relies on a bi-criteria solution? Is that part constitute the bottleneck? Also, does HK20 give bi-criteria solution whose update time is near-linear in k? If so, then maybe it's also an interesting angle to compare with their result, since yours may be viewed as a (strict) improvement of it. - In the end of Sec 1, it is mentioned that an algorithm for weighted k-median is presented in Sec 2. But I didn't find it - In Sec 3.1, it seems the algorithm only returns a bi-criteria solution. What's the procedure for making it a real feasible solution? How does that procedure affects the final time complexity?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I didn't find these explicitly discussed. A discussion of limitations, and possibly mentioning future directions, could be helpful. This paper is a theory paper and I don't see a potential negative societal impact.

Summary

This paper studies the $k$-median/means problems in fully dynamic settings. Clustering in fully dynamic setting is a recent hot topic, where fully dynamic $k$-center has been well studied in literature. However, little was known for fully dynamic $k$-median/means problems. Inspired by the static framework proposed by Mettu and Plaxton, where a minimum radius ball coverage strategy is used to obtain $t=O(logn)$ layers of representations for good approximation of the given $k$-median/means instance. This paper modifies the classic framework by Mettu and Plaxton and presents an $O(1)$-approximation algorithm for the fully dynamic $k$-median/means problems with $\tilde{O}(k)$ amortized update time and $\tilde{O}(k^2)$ worst case query time, which improves the previous coreset-based method with $\tilde{O}(k^2)$ worst case update time.

Strengths

1. This paper proposes simple but efficient approximation algorithm for the fully dynamic $k$-median/means problems with $\tilde{O}(k)$ amortized update time and $\tilde{O}(k^2)$ worst case query time, which improves the previous result with $\tilde{O}(k^2)$ update time and $\tilde{O}(k^2)$ query time. The authors also show that the update time of our algorithm is optimal up to polylogarithmic factors. 2. This paper gives detailed experimental evaluation of fully dynamic k-median algorithms for general metrics and shows that the proposed framework is more efficient than previous ones.

Weaknesses

1. The techniques used in this paper seem to rely heavily on the minimum ball coverage method by Mettu and Plaxton. 2. The challenges for obtaining good update time and query time is not well discussed. 3. The theoretical analysis is not an easy read in a limited time. The intuition behind the analysis and algorithm before going into the details of lemmas and proofs should be given before the proofs.

Questions

1. In each insertion, why should the data point to be inserted added to each layer $i \in [t]$ instead of one of the $t$ layers? 2. Can the authors discuss the challenges for applying the Mettu's and Plaxton's method for solving the fully dynamic $k$-clustering problems?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Since this is a theoretical paper, I don't think there is potential negative societal impact of this paper.

Summary

Fully dynamic k-clustering in O(k) update time This paper studies fully dynamic k-clustering. It gives a fully dynamic algorithm that maintains O(1)-approximate solutions to k-median and k-means with \tilde O(k) amortized update time and \tilde O(k^2) worst-case query time. On the negative side, the authors showed that the Omega(k) amortized update time is required if one needs to achieve O(1)-approximation ratio and poly(k) query time. So they gave the optimal update time, and the time improves the prior best-known update time of O(k^2). The authors also did experiments to complement the theoretical analysis. The dynamic algorithm is built on the static algorithm of [27]. It runs for many iterations. In each iteration i, the algorithm samples a set S_i of points and creates a set of smallest-radius balls around the samples so that the balls cover at least beta fraction of the remaining points, for a constant beta. The algorithm then removes the covered points and repeats the process. This gives a partition of the points into \tilde O(k) balls. They construct an assignment that maps every point to its ball center. Then a k-median or k-means solution can be constructed using the centers only. The dynamic algorithm maintains the tree-structure constructed in the static algorithm in a lazy manner by allowing some slack at many places. It needs to rebuild the tree from some layer if the cost of the assignment at that layer or above becomes bad. On average, it needs many updates for the algorithm to rebuild a tree from some layer, giving a good amortized update time.

Strengths

Overall, the paper gives a tight update time of \tilde O(k) for the fully dynamic k-clustering problem, using elegant techniques. This is a solid accept.

Weaknesses

The hidden approximation ratio is a little big.

Questions

1. Can you give a rough bound on the approximation ratio of the algorithm? 2. What happens if each update contains a batch of p points? Can you achieve an update time of O(p + k), instead of O(pk)?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

No limitations.

Summary

This paper considers the dynamic version of the $k$-median and the $k$-means clustering problem in an arbitrary metric space. The authors provide an $O(k)$ amortized time (which is near optimal based on a lower bound that the authors provide) for insertions and deletions of points and a query time of $O(k^2)$. This is an improvement of the recent result by Henzinger and Kale, ESA 2020 which provided a dynamic algorithm with a worst case $O(k^2)$ update time. The algorithm in this paper is based on making the algorithm of Mettu and Plaxton dynamic. The authors also provide implementations of their algorithm as well as prior works (including a coreset construction algorithm) and then provide an empirical performance analysis of these algorithms.

Strengths

This paper is providing a near-optimal bound for amortized update time for dynamic k-means and k-median clustering problems. The authors provide implementations of their algorithm as well as prior works which is very useful.

Weaknesses

In terms of techniques, the methods used are adaptation of an existing algorithm of Mettu and Plaxton and perhaps somewhat incremental in nature.

Questions

My questions were answered in a previous review cycle

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

NA