Near-Optimal $k$-Clustering in the Sliding Window Model

Summary

This paper proposes the first near-optimal $(1+\varepsilon)$-approximation algorithm for $(k, z)$-clustering problem in the sliding window model. The core part is the $(1+\varepsilon)$-coreset of $(k, z)$-clustering in the sliding window model which is based on an online coreset algorithm for $k$-clustering problem. This paper gives strict proof for the proposed algorithm and experimental results manifest its efficiency. In short, the theory aspect of this paper is solid enough.

Strengths

(1) This paper gives the first $(1+\varepsilon)$-approximation algorithm for $(k, z)$-clustering in the sliding window, which improves the existing results in two aspects including accuracy and space. (2) The space $\frac{k}{\min (\varepsilon^4, \varepsilon^{2+z}) }$ of $(1+\varepsilon)$-coreset for $(k, z)$-clustering in the sliding window almost matches the lower bound $\Omega \left(\frac{k}{\varepsilon^2} \log{n}\right)$. (3) Strict proof is provided and experimental results are sufficient. (4) The paper is well-written and well-organized.

Weaknesses

(1) Some symbol is not explained, like $[ \Delta ]^d$. (2) The merge-and-reduce framework lacks some citations.

Questions

In Line 92-93, Theorem 1.1 presents the word space $\frac{k}{\min(\varepsilon^4, \varepsilon^{2+z})} \text{poly} \log \frac{n \Delta}{\varepsilon}$. For $k$-median and $k$-means, $z$ is equal to $1$ and $2$ respectively. No matter $z$ is $1$ or $2$, the space should be $\frac{k}{\varepsilon^4} \text{poly} \log \frac{n \Delta}{\varepsilon}$ since $\varepsilon \in (0, 1)$. How can you achieve $\frac{k}{\varepsilon^2} \text{poly} \log \frac{n \Delta}{\varepsilon}$? In addition, for $(k, z)$-clustering, $z=1$ does not correspond to $k$-median when $\mathrm{dist}$ represents the Euclidean distance, since $k$-median is $\ell_1$-norm.

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

3 good

Presentation

3 good

Contribution

3 good

Limitations

See Weaknesses and Questions.

Summary

This paper studies the $k$-clustering problem in sliding window model. In sliding window model, a window of size $W$ is given to capture the most recent $W$ updates in the stream, where good clustering approximation should be maintained in the window with small space complexity. In previous work, in order to achieve an $(1+\epsilon)$ approximation for $(k,z)$-clustering problem in sliding window, a space complexity of $\frac{kd+d^{Cz}}{\epsilon^3}polylog(W,\Delta,\frac{1}{\epsilon})$ for some constant $C \ge 7$. In this work, the authors propose a coreset-based method, which gives an $(1+\epsilon)$-approximation for the $(k,z)$-clustering problem in sliding window model with space complexity $\frac{k}{min(\epsilon^4,\epsilon^{2+z})}polylog(\frac{n\Delta}{\epsilon})$, which is independent of the window size and nearly matches the lower bound of the space used by the offline coreset construction.

Strengths

1. The presented result significantly improves the space complexity of previous work with $(1+\epsilon)$-approximation guarantee on the clustering quality in sliding window model. Besides, this is the first approximation result that can achieve a space complexity independent of the window size $W$. In practical settings, since $\Delta$ is usually assumed to be bounded by $poly(n)$, the presented result can nearly match the lower bound space complexity required for any $(1+\epsilon)$-online coreset construction for $(k,z)$-clustering problem. 2. The extensive experimental results on real world datasets show that the proposed method is more efficient than previous ones.

Weaknesses

1. The techniques used in this paper seem to rely heavily on the current SOTA method for offline coreset construction [1] (using ring structures and independent sampling method) and the consistent approximation scheme proposed by Meyerson et al. [2]. 2. The challenges for merge and reduce operations is not discussed comprehensively in the literature. [1] Adam Meyerson. Online facility location. In 42nd Annual Symposium on Foundations of Computer Science, FOCS, pages 426–431. IEEE Computer Society, 2001. [2] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1038–1051, 2022.

Questions

1. It seems that the $O(log\Delta)$ dependence on the space complexity comes from the Meyerson approach (for obtaining the consistent approximation), where a guess-and-double process is used to obtain an estimation of the cost of an optimal solution. Is the $O(log\Delta)$ term necessary in the proposed method and is there any other method that can avoid guessing $O(log\Delta)$ times for the optimal clustering cost (for example by calling a single-criteria approximation algorithm with large approximation ratio to serve as the upper bound for optimal clustering cost)? 2. Can the authors explain more about the challenges when directly applying the reduce and merge method for each block of the divided data points in a stream without using an "inverse" operation? 3. I am curious about whether, in the sliding window model, the space complexity is more critical to consider compared to the time complexity. As I am not very familiar with this model, I would appreciate some insights on this matter.

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

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

4 excellent

Contribution

3 good

Limitations

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

Summary

This paper studies $k$-means and $k$-median clustering in the sliding window, and proposes an $(1+\varepsilon$)-approximation algorithm on the top of an coreset maintained through the stream. The space complexity is roughly $k/\text{poly}(\varepsilon) \cdot \text{poly}\log n$ where $n$ is the number of points, coming together with an nearly-tight lower bound.

Strengths

- The paper is well-written in general, most parts are clear and well-organized. - The results are interesting and significant. I did not read the entire proof, but checking the key steps convince me the result should be correct. I am happy to go back to proof details if any concern comes up. - It is a plus for a theory paper to have experiments. The space consumption is reduced a lot with some compromise on the clustering performance.

Weaknesses

- I am confused by line 388 389, it seems that the window size is too close to the stream size. Though theoretically the window size is not an important parameter, but doing this converges back to the streaming model. - After staring at it for a while, I do not think either of the algorithm or lower bound applies to the $k$-center clustering. Then is it OK to have $k$-clustering as in the title? The authors can either convince me this result holds / has impact on $k$-center clustering, or show me a bunch of work that does not include $k$-center in $k$-clustering. - I think it is good to make clear of the notation, especially when it first appears. In the abstract, maybe clarify what $z, \Delta$ is.

Questions

- Will the codes be made public? - Can you add an open problem section?

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

3 good

Presentation

3 good

Contribution

3 good

Limitations

I would appreciate this as a basically-complete theory work. There are some limitations on the experiments, but not a hurdle on assessing the contribution of this paper.

Summary

The paper proposes an near-optimal algorithm to build (1+$\epsilon$)-online coreset for k-clustering problem, and apply it to the sliding window model. The (near) optmality is established by a matching lower bound, also proved in the paper. A coreset is a compression of a dataset, such that any clustering centers will induce similar cost over the coreset and the original dataset. The (insertion-only) online coreset problem aims to build a coreset incrementally for a data stream, such that the coreset property (i.e., cost approximation) holds at any time point The main algorithm borrows lots of ideas from paper [24] ("*A New Coreset Framework for Clustering*"), which proposes a framework for building (offline) coresets and can be roughly described as follows: 1. Given a dataset, find a constant-approx clustering solution $A$ on it. 2. For each cluster induced by $A$, divide it into rings by distance to the center, such that all points in a same ring have roughly the same distance to the center. 3. Group rings at the same level from each cluster, then do importance sampling on the group. The sampled points (with scaled weights) will be the output coreset. For analysis, [24] shows that: as long as you can find a small "$A$-approximate centroid" $C$ (which is essentially something like a $\epsilon$-net restricted to part of the dataset), then you can have a small coreset. The paper essentially adapts the algorithm from [24] to the online setting 1. To get an constant-approx clustering in the online setting, the paper adopts a bi-criteria variant of Meyerson's algorithm for online facility location. Here the algorithm could produce more than k centers, but this is not an issue for bounding the coreset size since it only adds a constant factor. 2. The importance sampling step is mostly the same as described before, just in an online fashion. This gives the online coreset construction. 3. Finally, to apply it in the sliding window model, the paper breaks the input stream into blocks, then apply the online coreset construction in the reverse order on each block, and merge each block's coreset also in the reverse order (and keep only those within the window). I don't have time to look into the details of the lowerbound construction, however, it appears to be an adaptation of the offline bound from [23] ("*Towards optimal lower bounds for k-median and k-means coresets*").

Strengths

I think the main contribution is mostly in the theory side. The problem studied is important and well-motivated. It's nice to see that the result of [23] and [24] can be ported to the online setting. This requires quite some non-trivial work and the paper is able to identify an optimal choice of parameters, which results in an asymptotically optimal algorithm.

Weaknesses

As mentioned in the Summary, the main idea seems to be an (arguably) straightforward adaptation of [24], which somewhat limits the novelty. Also, I feel the experiment section is kinda redundant or even harmful to the paper's contribution. The proposed algorithm is not acutally implemented (in particular, the RingSample Alg, which is a core part of the proposed algorithm). It seems that the performance gain comes only from discarding points outside the sliding window, especially when compared with the histogram-based algorithm. - If the authors are able to implement their algorithm in a more meaningful way, and if it indeed produces better result on some realworld dataset, then I would be happy to increase my rating. Otherwise, I feel it's better to just remove the experiment section completely and present the paper as a theoretical contribution. Lastly, I believe the writing can be improved a lot. It seems the draft may have been finalized hastily, with instances of noticeable cutting and pasting to meet the page limit. This renders the main body insufficiently self-contained and challenging for readers unfamiliar with [24] (and not dive into the appendix proof). For example, it's hard to get much intuition why RingSample algorithm (Alg. 1) works unless a reader already knows the result of [24].

Questions

Some other comments. - I would recommend the authors to at least give a sketch of [24]'s idea before describing the RingSample algorithm. - I recommend to have "coreset" formally defined somewhere. - The notation $\mathrm{Cost}(X,Y)$ is never formally defined in the paper. Although I can guess what it is, it's better to define it somewhere as it is used frequently. - line 224: Same as above for $\mathrm{Cost}_{|S|\leq k}(X, S)$. - line 227-245: Many symbols defined here are not used at all in the main body. Please move them to the supplementary where they are actually used in the proof. Here they only distracts readers' attention. - line 233-236: $R_I(C_i)$ and $R_O(C_i)$ have the same definition. - line 243: I would write $G_{j, \mathrm{min}}$ and $G^O_b$ as union of some $R_{i,j}$'s rather than introducing a "$x$" there. It feels like you can take some $x$ from a $R_{i,j}$ while in fact it's all-or-nothing. - line 248: Lemma 2.2: what is $G$? - Section 3 (Experiment): My suggestion to the authors is to throw the experiment section to appendix or simply remove it, so you can have more space to enhance the readability of the theory part.

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

2 fair

Contribution

3 good

Limitations

N/A