Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings

David P. Woodruff; Liudeng Wang; Samson Zhou; Vincent Cohen-Addad

REVIEW 3 major objections 6 minor 54 references

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings

T0 review · 3 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that streaming algorithms for (k,z)-clustering and Lp subspace embeddings can match offline algorithms in both memory and per-item update time, with memory independent of stream length and aspect ratio.

desk verdict A genuinely new framework with impressive claimed bounds, but the space proof for the merge-and-reduce tree has a real gap that needs patching before the main theorems can be taken at face value. read the letter →

arxiv 2504.16229 v1 pith:2IAMVTQ6 submitted 2025-04-22 cs.DS

Vincent Cohen-Addad , Liudeng Wang , David P. Woodruff , Samson Zhou This is my paper · ORCID

classification cs.DS MSC 68W2768W2068Q25

keywords streamingalgorithms(kz)-clusteringcoresetssubspaceembeddingsLewisweightsmerge-and-reducesensitivitysamplingglobalencoding

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that two classic data-summarization tasks, Euclidean (k,z)-clustering and Lp subspace embeddings, can be run on an insertion-only stream with the same asymptotic memory and update time as their offline versions. For clustering, the proposed one-pass algorithm uses $\tilde{O}\left(\frac{dk}{\min(\varepsilon^4,\varepsilon^{z+2})}\right)$ words of memory, a bound free of the stream length $n$ and the aspect ratio $\Delta$, and amortized update time $d\log(k)\cdot\mathrm{polylog}(\log(n\Delta))$, an exponential improvement over prior streaming algorithms. For subspace embeddings, it claims $\tilde{O}(d^2/\varepsilon^2)$ words for $p\le 2$ and $\tilde{O}(d^{p/2+1}/\varepsilon^2)$ words for $p>2$, with $O(d)$ amortized update time, matching known lower bounds. If these claims hold, the long-standing question of whether streaming inherently costs extra space or time for these problems is answered in the negative.

What carries the argument

The load-bearing object is the global encoding: instead of maintaining a separate constant-factor approximation for each node of the merge-and-reduce tree, the algorithm reuses one global center set $C'$ (for clustering) or one global subspace embedding $M$ (for embeddings) to encode every subtree. For clustering, each point is represented as its closest center in $C'$ plus a coordinatewise rounded offset stored by exponent, so a coreset point costs $O(\log k + d\log(1/\varepsilon'))$ bits; for subspace embeddings, rows are first preconditioned by a well-conditioned basis and then rounded similarly. A companion mechanism is the reduction of $(k,z)$-clustering sensitivity to $(k,z)$-medoids sensitivity, which lets the algorithm compute crude sensitivity estimates in constant-factor approximation using local search plus a coarse quadtree with $O(1)$ levels. These components together carry the claimed independence from $n$ and $\Delta$.

What would settle it

Take a stream whose prefix splits into $m\approx \log\log n$ well-separated clusters and run the clustering algorithm with one global center set; compute for each subtree the quantity $|\mathrm{cost}(X'_i,C)-\mathrm{cost}(X_i,C)|$ and compare it with $\varepsilon/\mathrm{poly}(\log\log n)\cdot\mathrm{cost}(X,C)$. If any single part violates that bound while the sum stays small, the space-optimal streaming claim collapses, because this directly tests the per-part error bound needed by Lemma 2.8.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that a two-stage sampling pipeline—an initial crude sensitivity filter that shrinks the stream to $n^{1-\Omega(1)}$ points, followed by a refined sampling step that reduces it to $\mathrm{polylog}(n)$ points—can feed a merge-and-reduce tree whose nodes are stored in a global encoding. The encoding writes every point $x$ as its nearest center from a single constant-factor center set $C'$ plus an offset whose coordinates are rounded to powers of $(1+\varepsilon')$; storing only exponents and the center identity makes each point cheap while keeping total error additive, $\varepsilon/\mathrm{poly}(\log\log n)$ times the global cost. The same pattern, with a well-conditioned preconditioner and rounded rows, yields the subspace-embedding result. The paper therefore claims that space usage can be $O_{k,d,\varepsilon}(1)$ words for clustering and matching offline space for Lp embeddings, while update time drops to $d\log k\cdot\mathrm{polylog}(\log(n\Delta))$ and $O(d)$, respectively.

Load-bearing premise

The argument assumes a single global center set can be used to encode every subtree of the merge-and-reduce tree with per-subtree rounding error at most $\varepsilon/\mathrm{poly}(\log\log n)$ times the whole-prefix cost, so errors do not compound over the tree's $O(\log\log n)$ levels; the proof text gives only a sum-of-errors bound, so that per-part bound is not established as written.

Editorial extensions

If this is right

The streaming $(k,z)$-clustering space bound becomes independent of $n$ and $\Delta$, using $\tilde{O}(dk/\min(\varepsilon^4,\varepsilon^{z+2}))$ words and matching the best offline coreset size.
The amortized update time $d\log(k)\cdot\mathrm{polylog}(\log(n\Delta))$ is the first sublinear-in-$k$ update time for insertion-only clustering, and it gives the fastest known offline $(k,z)$-clustering runtime of $nd\log(k)\cdot\mathrm{polylog}(\log(n\Delta))$.
For Lp subspace embeddings, streaming space matches offline bounds: $\tilde{O}(d^2/\varepsilon^2)$ words for $p\le 2$ and $\tilde{O}(d^{p/2+1}/\varepsilon^2)$ words for $p>2$, with $O(d)$ amortized update time.
Because the clustering coreset is maintained for every prefix, the algorithm outputs an $O(z)$-approximation to the optimal clustering at every time in the stream, not just at the end.
When $k<1/\varepsilon^2$, the algorithm's black-box reduction can switch to alternative coreset constructions, giving a smooth transition between different regimes of $k$ and $\varepsilon$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the per-part error bound in the global-encoding lemma can be established by a sharper error-splitting argument, the same encoding strategy is likely to extend to other merge-and-reduce-based streaming problems such as low-rank approximation, where per-node encodings currently multiply space by polylog factors.
The crude-sensitivity two-stage pipeline suggests a broader design principle: spend most of the per-item budget on a rough filter and run expensive sensitivity estimates only on the shrunken stream; this could be adapted empirically to problems like k-center clustering or correlation clustering.
For fully dynamic streams with both insertions and deletions, the algorithm's inability to maintain a single global center set over changing prefixes is the main obstacle; a dynamic analogue of the global encoding would be a natural next target.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. First, the algorithmic idea is genuinely new and, if the proof can be patched, it would close the streaming/offline gap for clustering and subspace embeddings. Second, the current manuscript has a proof gap in the space analysis: Theorem 2.9 appears to count only one encoded coreset, while the merge-and-reduce tree stores multiple coresets over the stream. I think this is fixable, but as written the main theorem is not fully established.

What is new and good: the crude-then-refined sampling pipeline with a global encoding is a real step forward. Previous online sensitivity sampling had poly(k, log n) update time or polylog n space; here the claimed update time is d log k polylog(log nDelta) and the claimed word space is independent of n. The subspace-embedding side has a clean precondition-then-round encoding that is also worth attention. The paper is honest about relying on prior results like online sensitivity sampling and online Lewis weight sampling, and those are independent published theorems.

Where the soft spots are, in proportion: Lemma 2.8 states a per-part error bound but its proof only proves a sum bound. For the final correctness guarantee, the sum bound over m = poly(log log nDelta) parts is actually what you need, so this is mostly a misstatement that should be rewritten, not a fatal flaw. The more important issue is the space bound in Theorem 2.9. The sampled stream S' has length m = O(dk^2/epsilon^2 log^3(nDelta)), so the merge-and-reduce tree has height O(log log nDelta), and standard merge-and-reduce keeps one encoded coreset per level until the end of the stream. The theorem's space expression looks like it counts only the final coreset, not the sum over all levels. The stress-test note claims this reintroduces n-dependence through a polylog(log nDelta) factor. In words, that factor is L^c/log(nDelta) for L = polylog(log nDelta), which is o(1), so the abstract's O(dk/min(...)) word bound might still survive. But the proof needs to actually show that the per-level sum is absorbed, and it currently does not. The subspace section has the same merge-and-reduce structure, so it likely needs the same repair. There are also small constant-factor slips in Lemma 2.6, but they do not change the argument.

Who is this for: people working on streaming clustering and streaming linear algebra. They should read it carefully, but not cite the main theorems as established until the space analysis is fixed. This paper deserves a serious referee: the framework is plausible, the claimed results are important, and the identified gaps look repairable.

Referee Report

3 major / 6 minor

Summary. The paper proposes a unified framework for insertion-only streaming algorithms for Euclidean (k,z)-clustering and Lp subspace embeddings. For clustering, it claims a one-pass algorithm using O~(dk/min(ε^4, ε^{z+2})) words of memory independent of n and the aspect ratio Δ, with amortized update time d log(k) polylog(log(nΔ)) (Theorem 1.1, formalized in Theorem 3.22). For subspace embeddings, it claims O(d) amortized update time and O~(d^2/ε^2) words for p ≤ 2, or O~(d^{p/2+1}/ε^2) words for p > 2 (Theorem 1.3, formalized in Theorem 4.19). The technical route is: crude sensitivity approximations reduce the stream to length n^{1-Ω(1)}; refined online sensitivity/Lewis-weight sampling reduces it further to polylog(n); merge-and-reduce is then run on this short stream; and a global constant-factor encoding is used so that the O(log log nΔ) levels of the merge-and-reduce tree do not multiply the space by log(nΔ). The clustering part contains a fast medoids-based sensitivity oracle and a crude quadtree routine to achieve the polylog(log nΔ) update time, while the subspace-embedding part uses preconditioned rounding and online Lewis weights.

Significance. If the proofs are completed, the results would be significant: they claim to close the gap between offline and streaming complexity for two fundamental problems, achieving space bounds matching offline coreset constructions and update times with exponentially better dependence on k and log(nΔ) than previous work. The global-encoding idea is elegant and plausibly reusable. The paper also claims the fastest known offline runtime for (k,z)-clustering as a byproduct. The main reservations are proof gaps in the global-encoding lemmas and in the space accounting for the merge-and-reduce tree; these are load-bearing for the headline space-independent-of-n claims, but they appear repairable rather than fatal.

major comments (3)

[Section 2.3, Lemma 2.8] Lemma 2.8 is stated as a per-part bound: for every i and every C, |cost(X'_i,C)-cost(X_i,C)| ≤ ε/poly(log log ndΔ) · cost(X,C). The proof establishes only an aggregate bound: from Lemma 2.6 applied to the whole X it obtains |cost(X',C)-cost(X,C)| ≤ ε/poly(log log ndΔ) · cost(X,C), and then uses the triangle inequality to bound the sum over i by ε·cost(X,C). This does not imply the per-part statement, which can fail when a part Xi is far from the global constant-factor center set C'. The merge-and-reduce correctness argument needs a bound on the error of each encoded coreset; please restate the lemma as an aggregate error bound and show explicitly in Theorem 2.9 that using the aggregate bound at each of the O(log log nΔ) levels, with accuracy ε/poly(log log nΔ), gives total error ε. Lemma 4.14 in Section 4.2 has exactly the same statement/proof mismatch and needs the same repair.
[Section 2.3, proof of Theorem 2.9 (last paragraph)] The last paragraph of the proof of Theorem 2.9 does not establish the stated space bound. The theorem states O(dk log(nΔ)) + f(n,d,Δ,k, polylog(log(ndΔ))/ε, z)·polylog(...) bits, where the accuracy parameter inside f is amplified by polylog(log nΔ). The proof instead bounds the number of sampled points in S' by O(dk^2/ε^2 log^3(nΔ/ε)) and applies Lemma 2.7 to that quantity. This omits two effects: (i) merge-and-reduce stores one encoded coreset per node of the tree, i.e., O(log |S'|) = O(log log nΔ) coresets, each of size f(ε/poly(log log nΔ)); and (ii) the accuracy amplification must be substituted into f. The same gap appears in the proof of Theorem 4.15, where the space bound is obtained from the size of the sampled stream rather than from a sum over the stored encoded coresets. Please provide the full accounting, including the bits-to-words conversion that cancels the log(nΔ) factors.
[Section 3.3, Theorem 3.16 and Lemma 3.21] Theorem 3.16 is a new statement (an N^α-approximation algorithm for (k,z)-clustering in O(nd log(nd)) expected time) that is not proven; the paragraph following it only sketches how to modify [CLN+20]. Since Lemma 3.21 and therefore the d log(k) polylog(log nΔ) update time of Theorem 3.22 depend entirely on this theorem, it cannot be cited as a black box at this level of generality. Please provide a full proof or a precise statement of which result in [CLN+20] gives the claim, including the failure probability and the range of z for which the crude quadtree with O(1) levels yields the N^α approximation.

minor comments (6)

[Algorithm 2, line 1] The parameter λ is set to O(k/ε^2 log k log n), but the proof of Theorem 2.9 uses the sample bound O(dk^2/ε^2 log^3(nΔ/ε)) from Theorem 2.4, which requires λ to depend on d. Please adjust λ to O(dk/ε^2 log k log n) (as in Algorithm 5) or explain why the d factor is unnecessary.
[Lemma 2.6, proof] The sentence 'Since C′ is a constant-factor approximation ... cost(C,X′)≤γ·cost(C,X)' should read 'cost(C′,X)≤γ·cost(C,X)'. As written, the proof attributes to C′ a property that is not the defining property of a constant-factor approximation.
[Lemma 3.1, proof] The inequality ∥c′−p∥^z ≤ 2^z(∥c′−c∥_2^2 + ∥p−c∥_2^2) should have the z-th power on the two distance terms rather than squares; otherwise the subsequent 2^{z+1} factor does not follow from the displayed line.
[Algorithm 6, line 13 and Lemma 3.18] The update for ŝ(x) has an unbalanced parenthesis in the printed expression ŝ(x) ← max(ŝ(x), d^{z/2}·ζ^{βz}/(Ψ+nβ·(d^{z/2}·ζ^{βz})). Also, the proof of Lemma 3.18 refers to 'Φ' where the lemma uses 'Ψ'.
[Figure 4] The rows labeled 'Theorem 1.1 (this work), p≤2' and 'Theorem 1.1 (this work), p>2' in the subspace-embedding table should refer to Theorem 1.3, not Theorem 1.1.
[Section 2.3, first paragraph] There is a duplicated phrase: 'Let C′ be a set of k centers that is a set C′ of k centers that is a constant-factor approximation...' Please remove the repetition.

Circularity Check

0 steps flagged · score 1.0 of 10

No material circularity: the derivation rests on independently proved prior theorems and self-contained lemmas, with only a proof gap in Lemma 2.8.

full rationale

The paper's central claims rest on two black-box pillars: online sensitivity sampling (Theorems 2.3 and 2.4, cited to [CWZ23]) and online Lewis weight sampling (Theorems 4.5 and 4.6, cited to [WY23]). These are prior published theorems with their own proofs; they are not defined in terms of the present results, and the fact that some authors overlap with the present paper does not by itself make the dependence circular. The global-encoding step (Section 2.3) recomputes a constant-factor approximation of the current prefix and rounds offsets with respect to that one center set; this is a standard bootstrap, not a fitted input renamed as a prediction. Lemma 2.6 gives a self-contained rounding-error proof, and the claimed space bound follows from the paper's convention that a word is Theta(log(ndDelta)) bits, so O(dk log(nDelta)) bits is O(dk) words and the extra polylog(log(ndDelta)) factors are absorbed after word conversion. One genuine concern is that Lemma 2.8 states a per-part error bound but its proof only establishes the sum of errors over all parts; the quoted inequality in the proof bounds |cost(X'_i,C)-cost(X_i,C)| by a sum over all i, which is a proof gap rather than a circularity. For the same reason, Theorem 2.9's space accounting should be checked for whether it counts all stored tree nodes, but that is a correctness and rigor issue, not a reduction of the output to the input. No ansatz is smuggled in by citation: the rounding encoding is proved in Lemma 2.6, and the crude quadtree and fast local-search tools are cited to independent prior work. Overall the claimed predictions, namely an n-independent word count and fast amortized update time, are not by construction equivalent to the inputs, so the circularity score is 1.

Assumptions & free parameters 6 free parameters · 8 assumptions · 0 invented entities

The central claims rest on several black-box prior results: optimal coreset constructions, online sensitivity sampling, online Lewis weight sampling, and well-conditioned basis algorithms. These are standard domain assumptions from the literature and are not proved here. The algorithmic constants (sampling scales, rounding precision, quadtree ratios) are design parameters, not data-fitted values, but they are essential to the stated bounds. No new entities are introduced.

free parameters (6)

epsilon' (rounding precision in Algorithm 1) = poly(epsilon^z) / poly(k, log(ndDelta))
Chosen analytically to balance the approximation error from rounding offsets; not fitted to data, but a design parameter the space and time bounds depend on.
lambda (sampling scale for clustering) = O((k / epsilon^2) log k log n)
Sets sampling probability in Algorithm 2; chosen to make online sensitivity sampling yield the desired sample size.
zeta (quadtree side-length ratio) = n^{1-c} for a fixed constant c in (0,1)
Sparse quadtree with O(1/c) levels; used in RoughSens (Algorithm 6) to obtain crude sensitivity estimates.
kappa (quadtree distortion bound in RoughSens) = n^{alpha} for a fixed constant alpha in (0,1)
Determines the crudeness of sensitivity estimates; chosen so the tree has O(1) levels.
lambda_sub (sampling scale for subspace embeddings) = O((d / epsilon^2) log d log n)
Sets sampling probability in Algorithm 8 for online Lewis weights.
epsilon'_sub (subspace rounding precision) = poly(epsilon) / poly(d^p, log(nd))
Chosen to control rounding error after preconditioning in Algorithm 7.

assumptions (8)

standard math Generalized triangle inequality (Fact 1.4)
Used throughout the clustering proofs to bound distances after moving centers; a standard inequality.
standard math Hoeffding's inequality (Theorem 1.8)
Invoked for concentration bounds; standard probability tool.
standard math Johnson-Lindenstrauss lemma (Theorem 1.7)
Used for dimensionality reduction in the streaming algorithms; standard result.
domain assumption Coreset construction of CLSS22/HLW23 (Theorem 1.6)
The paper uses the existence of near-optimal offline coresets as a black box for the final space bound; not proved here.
domain assumption Online sensitivity sampling theorems of CWZ23 (Theorems 2.3, 2.4)
Provides the sum-of-sensitivities bound and the correctness of online sensitivity sampling; these are prior published results by the same authors, used as building blocks.
domain assumption Online Lewis weight sampling theorems of WY23 (Theorems 4.5, 4.6)
Provides the sum of online Lewis weights and the sampling guarantee for subspace embeddings; prior published result.
domain assumption Well-conditioned basis construction of DDH+09 (Theorem 4.9)
Used to precondition the subspace embedding before rounding; prior published result.
domain assumption Local search algorithm for clustering approximation (Theorem 3.4)
Used to find constant-factor approximations to (k,z)-medoids clustering; prior result.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings." pith.science (2026). https://pith.science/paper/2IAMVTQ6

@misc{pith2026250416229,
  author       = {Pith},
  title        = {Pith review of: Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2IAMVTQ6}},
  note         = {Machine review of arXiv:2504.16229}
}

abstract

We show that both clustering and subspace embeddings can be performed in the streaming model with the same asymptotic efficiency as in the central/offline setting. For $(k, z)$-clustering in the streaming model, we achieve a number of words of memory which is independent of the number $n$ of input points and the aspect ratio $\Delta$, yielding an optimal bound of $\tilde{\mathcal{O}}\left(\frac{dk}{\min(\varepsilon^4,\varepsilon^{z+2})}\right)$ words for accuracy parameter $\varepsilon$ on $d$-dimensional points. Additionally, we obtain amortized update time of $d\,\log(k)\cdot\text{polylog}(\log(n\Delta))$, which is an exponential improvement over the previous $d\,\text{poly}(k,\log(n\Delta))$. Our method also gives the fastest runtime for $(k,z)$-clustering even in the offline setting. For subspace embeddings in the streaming model, we achieve $\mathcal{O}(d)$ update time and space-optimal constructions, using $\tilde{\mathcal{O}}\left(\frac{d^2}{\varepsilon^2}\right)$ words for $p\le 2$ and $\tilde{\mathcal{O}}\left(\frac{d^{p/2+1}}{\varepsilon^2}\right)$ words for $p>2$, showing that streaming algorithms can match offline algorithms in both space and time complexity.

Figures

Figures reproduced from arXiv: 2504.16229 by the authors.

**Figure 2.** Table of (k, z)-clustering algorithms on data streams, omitting linear dependencies in the dimension d. We remark that [HK20, BCLP23, BCF24] can handle the fully-dynamic setting, whereas ours cannot. However, our algorithm uses sublinear space while theirs does not. Additionally, Theorem 1.1 is the first result to achieve (k, z)-clustering on insertion-only streams using Ok,d,ε(1) words of space, i.e., space usage i… view at source ↗

**Figure 3.** Table of (k, z)-clustering algorithms on insertion-only streams. We summarize existing results with z = O (1), ∆ = poly(n), and the assumption that k > 1 ε z for the purpose of presentation. Moreover, we note that Theorem 1.1 also implies that we can efficiently compute the approximately optimal centers for (k, z)-clustering in the incremental setting as well. In particular, given an insertion-only stream of n poin… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Table of Lp subspace embedding algorithms on insertion-only streams. We summarize existing results with κ = poly(n) for the purpose of presentation. 1.2 Technical Overview In this section, we provide a high-level intuition behind our framework and how to efficiently im…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 40 canonical work pages

[1]

k-means++: the advantages of careful seeding

David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 1027--1035, 2007

work page 2007
[2]

Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenstrauss lemma

Luca Becchetti, Marc Bury, Vincent Cohen - Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenstrauss lemma. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019...

work page 2019
[3]

Fully dynamic k-median with near-optimal update time and recourse

Sayan Bhattacharya, Mart \' n Costa, and Ermiya Farokhnejad. Fully dynamic k-median with near-optimal update time and recourse. CoRR , abs/2411.03121, 2024

arXiv 2024
[4]

Fully dynamic k-clustering with fast update time and small recourse

Sayan Bhattacharya, Mart \' n Costa, Naveen Garg, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering with fast update time and small recourse. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 216--227, 2024

work page 2024
[5]

Fully dynamic k-clustering in O (k) update time

Sayan Bhattacharya, Mart \' n Costa, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering in O (k) update time. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS , 2023

work page 2023
[6]

Woodruff, and Samson Zhou

Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 517--528, 2020

2020
[7]

Efficient coreset constructions via sensitivity sampling

Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. Efficient coreset constructions via sensitivity sampling. In Asian Conference on Machine Learning, ACML , pages 948--963, 2021

work page 2021
[8]

Streaming coreset constructions for m -estimators

Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus. Streaming coreset constructions for m -estimators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 62:1--62:15, 2019

work page 2019

Show all 54 references

[9]

Razenshteyn, and David P

Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, and David P. Woodruff. Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 318...

2016
[10]

Jon Louis Bentley and James B. Saxe. Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms , 1(4):301--358, 1980

1980
[11]

Query complexity of least absolute deviation regression via robust uniform convergence

Xue Chen and Michal Derezinski. Query complexity of least absolute deviation regression via robust uniform convergence. In Conference on Learning Theory, COLT , volume 134, pages 1144--1179, 2021

2021
[12]

Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu

Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC , pages 163--172, 2015

2015
[13]

On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications

Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput. , 39(3):923--947, 2009

2009
[14]

Fast and accurate k -means++ via rejection sampling

Vincent Cohen - Addad, Silvio Lattanzi, Ashkan Norouzi - Fard, Christian Sohler, and Ola Svensson. Fast and accurate k -means++ via rejection sampling. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS , 2020

2020
[15]

Improved coresets for euclidean k-means

Vincent Cohen - Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh - Omar. Improved coresets for euclidean k-means. In NeurIPS , 2022

2022
[16]

Towards optimal lower bounds for k-median and k-means coresets

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

2022
[17]

Cohen, Cameron Musco, and Jakub Pachocki

Michael B. Cohen, Cameron Musco, and Jakub Pachocki. Online row sampling. Theory Comput. , 16:1--25, 2020

2020
[18]

Cohen and Richard Peng

Michael B. Cohen and Richard Peng. l_p row sampling by lewis weights. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC , pages 183--192, 2015

2015
[19]

A new coreset framework for clustering

Vincent Cohen - Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In STOC : 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 169--182, 2021

2021
[20]

Woodruff, and Samson Zhou

Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Optimal algorithms for linear algebra in the current matrix multiplication time. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 4026--4049, 2023

2023
[21]

Clarkson and David P

Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC , pages 205--214, 2009

2009
[22]

Clarkson and David P

Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Symposium on Theory of Computing Conference, STOC , pages 81--90, 2013

2013
[23]

Woodruff, and Samson Zhou

Vincent Cohen - Addad, David P. Woodruff, and Samson Zhou. Streaming euclidean k -median and k -means with o( n) space. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 883--908, 2023

2023
[24]

Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney. Sampling algorithms and coresets for l_p regression. SIAM J. Comput. , 38(5):2060--2078, 2009

2009
[25]

Mahoney, and S

Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-based methods. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Al...

2006
[26]

Mahoney, and S

Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-error matrix approximation: Column-row-based methods. In Algorithms - ESA 2006, 14th Annual European Symposium, Proceedings , pages 304--314, 2006

2006
[27]

Settling time vs

Andrew Draganov, David Saulpic, and Chris Schwiegelshohn. Settling time vs. accuracy tradeoffs for clustering big data. Proc. ACM Manag. Data , 2(3):173, 2024

2024
[28]

A unified framework for approximating and clustering data

Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC , pages 569--578, 2011

2011
[29]

Schulman

Dan Feldman and Leonard J. Schulman. Data reduction for weighted and outlier-resistant clustering. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 1343--1354, 2012

2012
[30]

Simpler analyses of local search algorithms for facility location

Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility location. CoRR , abs/0809.2554, 2008

2008 arXiv
[31]

Smaller coresets for k-median and k-means clustering

Sariel Har - Peled and Akash Kushal. Smaller coresets for k-median and k-means clustering. Discret. Comput. Geom. , 37(1):3--19, 2007

2007
[32]

Fully-dynamic coresets

Monika Henzinger and Sagar Kale. Fully-dynamic coresets. In 28th Annual European Symposium on Algorithms, ESA , volume 173, pages 57:1--57:21, 2020

2020
[33]

On optimal coreset construction for euclidean (k,z) -clustering, 2023

Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for euclidean (k,z) -clustering, 2023

2023
[34]

On coresets for k-means and k-median clustering

Sariel Har - Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing , pages 291--300, 2004

2004
[35]

Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC , pages 1416--1429, 2020

2020
[36]

Dimensionality reduction for wasserstein barycenter

Zachary Izzo, Sandeep Silwal, and Samson Zhou. Dimensionality reduction for wasserstein barycenter. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS , 2021

2021
[37]

Fast image retrieval via embeddings

Piotr Indyk and Nitin Thaper. Fast image retrieval via embeddings. In International Workshop on Statistical and Computational Theories of Vision, ICCV Workshop , volume 120, 2003

2003
[38]

Extensions of lipschitz mappings into a hilbert space

William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. conference in modern analysis and probability (new haven, conn., 1982), 189--206. In Contemp. Math , volume 26, 1984

1982
[39]

Fully dynamic k-means coreset in near-optimal update time

Max Dupr \' e la Tour, Monika Henzinger, and David Saulpic. Fully dynamic k-means coreset in near-optimal update time. In 32nd Annual European Symposium on Algorithms, ESA , pages 100:1--100:16, 2024

2024
[40]

Almost-linear time approximation algorithm to euclidean k-median and k-means

Max Dupr \' e la Tour and David Saulpic. Almost-linear time approximation algorithm to euclidean k-median and k-means. CoRR , abs/2407.11217, 2024

2024 arXiv
[41]

Woodruff

Yi Li, Ruosong Wang, and David P. Woodruff. Tight bounds for the subspace sketch problem with applications. SIAM J. Comput. , 50(4):1287--1335, 2021

2021
[42]

Row sampling for matrix algorithms via a non-commutative bernstein bound

Malik Magdon - Ismail. Row sampling for matrix algorithms via a non-commutative bernstein bound. CoRR , abs/1008.0587, 2010

2010 arXiv
[43]

Meyer, Cameron Musco, Christopher Musco, David P

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou. Fast regression for structured inputs. In The Tenth International Conference on Learning Representations, ICLR , 2022 , 2022

2022
[44]

Meyer, Cameron Musco, Christopher Musco, David P

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou. Near-linear sample complexity for L$ _ p $ polynomial regression. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 3959--4025, 2023

2023
[45]

Razenshteyn

Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson-lindenstrauss transform for k -means and k -medians clustering. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC , pages 1027--1038, 2019

2019
[46]

Woodruff, and Taisuke Yasuda

Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda. Active linear regression for l_p norms and beyond. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 744--753, 2022

2022
[47]

Woodruff, and Samson Zhou

Sepideh Mahabadi, David P. Woodruff, and Samson Zhou. Adaptive sketches for robust regression with importance sampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 31:1--31:21, 2022

2022
[48]

L1 regression with lewis weights subsampling

Aditya Parulekar, Advait Parulekar, and Eric Price. L1 regression with lewis weights subsampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 49:1--49:21, 2021

2021
[49]

Improved approximation algorithms for large matrices via random projections

Tam \' a s Sarl \' o s. Improved approximation algorithms for large matrices via random projections. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Proceedings , pages 143--152, 2006

2006
[50]

Woodruff

Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 802--813, 2018

2018
[51]

Woodruff

David P. Woodruff. Sketching as a tool for numerical linear algebra. Found. Trends Theor. Comput. Sci. , 10(1-2):1--157, 2014

2014
[52]

Woodruff and Taisuke Yasuda

David P. Woodruff and Taisuke Yasuda. Online lewis weight sampling. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 4622--4666, 2023

2023
[53]

Woodruff, Peilin Zhong, and Samson Zhou

David P. Woodruff, Peilin Zhong, and Samson Zhou. Near-optimal k -clustering in the sliding window model. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS 2023 , 2023

2023
[54]

Space complexity of euclidean clustering

Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, and Zengfeng Huang. Space complexity of euclidean clustering. arXiv preprint arXiv:2403.02971 , 2024

2024 arXiv

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

k-means++: the advantages of careful seeding

David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 1027--1035, 2007

work page 2007

[2] [2]

Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenstrauss lemma

Luca Becchetti, Marc Bury, Vincent Cohen - Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the johnson-lindenstrauss lemma. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019...

work page 2019

[3] [3]

Fully dynamic k-median with near-optimal update time and recourse

Sayan Bhattacharya, Mart \' n Costa, and Ermiya Farokhnejad. Fully dynamic k-median with near-optimal update time and recourse. CoRR , abs/2411.03121, 2024

arXiv 2024

[4] [4]

Fully dynamic k-clustering with fast update time and small recourse

Sayan Bhattacharya, Mart \' n Costa, Naveen Garg, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering with fast update time and small recourse. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 216--227, 2024

work page 2024

[5] [5]

Fully dynamic k-clustering in O (k) update time

Sayan Bhattacharya, Mart \' n Costa, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering in O (k) update time. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS , 2023

work page 2023

[6] [6]

Woodruff, and Samson Zhou

Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 517--528, 2020

2020

[7] [7]

Efficient coreset constructions via sensitivity sampling

Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. Efficient coreset constructions via sensitivity sampling. In Asian Conference on Machine Learning, ACML , pages 948--963, 2021

work page 2021

[8] [8]

Streaming coreset constructions for m -estimators

Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus. Streaming coreset constructions for m -estimators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 62:1--62:15, 2019

work page 2019