- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies sliding-window coresets for clustering with outliers in streaming data. Its main contribution is the first nontrivial sliding-window coreset for this problem. The key idea is to reduce sliding-window design to a mergeable prefix-query summary and to modify an existing reduction so that merges move points only from explicit storage to the compressed part. The algorithm uses isolation, sparse, and vanilla layers with compact histories to support prefix queries and merges. Theoretically, it returns a coreset after every update with high probability, with space and size comparable to the insertion-only setting.
Validation is experimental. On five real datasets with injected synthetic outliers, for robust mean clustering, the method outperforms uniform sampling and an online vanilla coreset, and is slightly worse than an offline robust coreset while supporting sliding-window queries. The main limitation is that experiments cover only low-dimensional, medium-scale data with synthetic outliers, so generalizability is not fully demonstrated.
Critical strengths
The authors do clearly articulate the core idea in the Technical overview and the “Our idea” paragraph: reduce sliding-window design to a mergeable prefix-query summary, and ensure merges move points only from explicit storage to the compressed part. I approve this idea , but the key sentence is not intuitive enough, is not friendly to readers of other domain.
Strength. The paper establishes the first nontrivial sliding-window coreset for (k,z,m)-clustering, with space and coreset-size bounds comparable to the insertion-only setting. It also conveys a key conceptual insight—reduce sliding-window clustering to a mergeable prefix-query summary, and enforce monotone movement of points from explicit storage to the compressed part—which explains why the summary is mergeable and why outliers can be handled safely.
Critical weaknesses
The authors do not clearly and centrally state the problem addressed by this paper in the abstract, introduction, or a standalone problem definition section; instead, the problem setup is scattered across the Main result, the Technical overview, and several definitions.
The paper does not sufficiently demonstrate applicability or generalizability. The concrete algorithm is tied to Euclidean consistent hashing, finite-z sum objectives, Reduction I, and a vanilla coreset black box, with experiments only on z=2, low-dimensional, medium-scale data and synthetic outliers. A scope and generalizability discussion is needed.
there is no framework figure to clearly and intuitively experss the process of the work.
Questions for authors
How generalizable is the algorithm beyond Euclidean consistent hashing, finite-z sum objectives, and the vanilla coreset black box? Which components are essential limitations versus replaceable, and what are the main obstacles for general metrics, high-dimensional data, larger z, and realistic outlier patterns?
2 comments
Thanks for your feedbacks, my conserns are addressed.
The opening of the Introduction defines clustering with outliers and describes the sliding-window setting. The Introduction is self-contained in this regard. We revisit these concepts later to formalize the definitions used in the analysis.
We will add a generalizability discussion in the next version. Specifically, we discuss the following aspects from the experiments.
The setting: Euclidean k-means is arguably the most widely used clustering method, among all metric (k,z)-clustering variants. This also covers a wide range of practical applications. Moreover, given the similar structure among (k,z)-clustering, a good performance of k-means (z=2) often translates to other general z. More specifically, our analysis indicates that z=1 and settings without synthetic outliers are easier than those in our original experiments, and that increasing the dataset size poses no additional difficulty for the approximation guarantee. We therefore focused our original experiments on the more challenging settings.
The planted outlier: We also designed our experiments to test whether our algorithm can still achieve good approximation ratios under extreme outlier conditions, where baselines such as uniform sampling perform poorly. This demonstrates our generalizability to the worst-case outliers.
We will add a figure illustrating the framework in the revised version.