REVIEW 2 cited by
Nearly Optimal Dynamic $k$-Means Clustering for High-Dimensional Data
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We consider the $k$-means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space $\{1, 2, \ldots, \Delta\}^d$ can be dynamically inserted to or deleted from the dataset. For this problem, we provide a one-pass coreset construction algorithm using space $\tilde{O}(k\cdot \mathrm{poly}(d, \log\Delta))$, where $k$ is the target number of centers. To our knowledge, this is the first dynamic geometric data stream algorithm for $k$-means using space polynomial in dimension and nearly optimal (linear) in $k$.
Forward citations
Cited by 2 Pith papers
-
Coresets for Robust Clustering via Black-box Reductions to Vanilla Case
A black-box reduction turns any vanilla clustering coreset into an epsilon-coreset for clustering with m outliers, with size N times polylog plus min{O(km/epsilon), O(m/epsilon^{2z})}.
-
An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
A new MPC algorithm computes a constant-factor k-means approximation with exactly k centers in O(log log n log log log n) rounds and nearly linear global memory.
Discussion (0). Continue with ORCID to comment.