- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper speed up coreset construction for Euclidean clustering, subspace embedding and projection-cost preservation in insertion-only streams. The main idea is to down-sample the stream to elements using a coarse sampling scheme and then apply optimal sampling scheme. This allows to improve the update time (amortized analysis) while preserving the optimal space of the known methods.
The main improvement is to speed up the update time for the Euclidean -clustering problem improving the dependence on from poly(k) to poly(logk) and the dependence on from polylog(n\Delta) to polyloglog(n\Delta) - an exponential improvement. This further shows a separation between metric clustering which require time per update and Euclidean -clustering.
Using similar framework, but independent analysis, they improve the update time for subspace embedding and projection-cost preservation, where in the streaming model the input matrix arrive sequentially row-by-row.
Critical strengths
- The paper improves state-of-the-art algorithms for classical problems in the insertion-only streaming model: -clustering and coreset construction, subspace embedding and projection-cost preserving sketches.
- While the technical idea seems simple (crude sampling first and then refined sampling), the analysis is intricate and the combination of techniques is non-trivial.
Critical weaknesses
- The technical parts in the appendix are not easy to follow, and I think a more extensive technical overview is needed in the final version.
- The results should be placed in better context with previous work, for example what is the update time by taking state-of-the-art coreset construction for the offline settings and apply it with merge-and-reduce framework of HM04? This is omitted from the introduction (appear only in the technical sections). I think a more comprehensive table(s) that compare previous results with the current improvements is necessary and more generally, the authors should consider including a related work section which covers each one of the problems.
Questions for authors
- Do you think that the technical overview and related work can be improved during the rebuttal period?
- what is in Theorem 1.3, this is undefined.
- can you specify the regime (n,d,k) for which the term is neglected?
Thank you again for the review. We would appreciate any further comments on our response and revised manuscript. We would also be happy to elaborate on any remaining concerns.