{"id":"0ffcf3e3-0364-4916-b525-ae180009eb97","arxiv_id":"2504.16229","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Streaming algorithms for (k,z)-clustering and Lp subspace embeddings can match offline algorithms in space and time, removing all dependence on stream length n.","lead":"This paper gives streaming algorithms for clustering and subspace embeddings that use the same amount of memory and time as algorithms that see the whole dataset. If correct, it closes a long-standing gap between streaming and offline computation for these problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claimed n-independent space is unsupported: the merge-and-reduce tree on the polylog(n) sampled stream forces a poly(log log n) factor in the formal space bound.","rationale":"The reader's weakest-assumption analysis focuses on Lemma 2.8, where the proof bounds only the sum of per-part errors while the lemma claims a per-part bound. I agree that this is a genuine proof gap, but it appears secondary: the correctness argument can likely go through with the sum bound, since the total additive error across all parts is what matters when merging. The more load-bearing concern, in my reading, is that the formal space bound in Theorem 3.22 contains an explicit poly(log log(ndDelta)) factor through the accuracy parameter epsilon/poly(log log(ndDelta)) used inside f, and through the height of the merge-and-reduce tree on the sampled stream S' of length polylog(nDelta). Standard merge-and-reduce stores one encoded coreset per level, so the total space is O(L * f(epsilon/L)) = \\tilde{O}(dk L^{max(4,z+2)+1}/min(...)) words, which depends on n via L = O(log log nDelta). The proof of Theorem 2.9 does not appear to account for this sum over tree levels; it bounds space as if the global encoding stores only the final coreset. This affects the main advertised contribution, namely O_{k,d,epsilon}(1) words independent of n and Delta. The issue is fixable by restating the bounds with a poly(log log nDelta) factor, but the abstract and Theorem 1.1 as written overclaim. I therefore keep the reader's CONDITIONAL verdict: the approach is plausible and the gaps appear repairable, but the manuscript does not currently establish the headline space bound. My disagreement with the reader is about which assumption is most load-bearing, not about the existence of a gap.","tokens_in":43853,"tokens_out":20617,"duration_ms":193527,"concrete_test":"Recompute the space of Algorithm 2 by summing the encoded coreset sizes over all levels of the merge-and-reduce tree rather than taking only the final coreset. Let m = O(dk^2/epsilon^2 log^3(nDelta)) be the length of S', set block size B = f(epsilon/L) with L = ceil(log_2 m), and use the per-point bit count from Lemma 2.7 under the single global center set C'. If the total stored encoded points is Theta(L * B * polylog), then the space bound contains a poly(log log nDelta) factor and the claim of independence from n is false; if, alternatively, the authors exhibit a data structure that stores only O(B) encoded points at all times while still answering prefix queries, the claim survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and Theorem 1.1 claim (k,z)-clustering in \\tilde{O}(dk/min(epsilon^4, epsilon^{z+2})) words of memory, independent of n and the aspect ratio Delta. The formal statement, Theorem 3.22, instead gives O(dk log(nDelta)) + f(n,d,Delta,k, poly(log log(ndDelta))/epsilon, z) * polylog(...) bits. Substituting the coreset bound of Theorem 1.6 with accuracy epsilon/poly(L), where L := polylog(log(ndDelta)), yields f = \\tilde{O}(dk L^{max(4,z+2)} / min(epsilon^4, epsilon^{z+2})). Meanwhile, 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 m) = O(log log nDelta), and standard merge-and-reduce stores one encoded coreset per level. The total number of stored encoded points is therefore O(L * f(epsilon/L)) = \\tilde{O}(dk L^{max(4,z+2)+1}/min(...)), which still depends on n through L. The global encoding in Algorithm 2 removes the per-node overhead of storing separate center sets, but it does not reduce the number of stored coresets or the accuracy amplification epsilon/poly(log log nDelta) that enters f. The proof of Theorem 2.9 appears to bound space using the size of the final coreset rather than summing over all stored tree nodes. Separately, Lemma 2.8 is stated as a per-part error bound but its proof only establishes the sum of errors over all parts; this is a real proof gap, though a sum bound would likely suffice for correctness. The poly(log log nDelta) factor in the space bound is the more load-bearing issue because it directly contradicts the paper's central claim of space independent of n and Delta.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":44242,"tokens_out":14098,"duration_ms":128340,"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":[{"comment":"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":"Section 2.3, Lemma 2.8"},{"comment":"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":"Section 2.3, proof of Theorem 2.9 (last paragraph)"},{"comment":"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.","section":"Section 3.3, Theorem 3.16 and Lemma 3.21"}],"minor_comments":[{"comment":"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.","section":"Algorithm 2, line 1"},{"comment":"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.","section":"Lemma 2.6, proof"},{"comment":"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.","section":"Lemma 3.1, proof"},{"comment":"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 'Ψ'.","section":"Algorithm 6, line 13 and Lemma 3.18"},{"comment":"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":"Figure 4"},{"comment":"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.","section":"Section 2.3, first paragraph"}],"recommendation":"major_revision","confidential_remarks":"The three major issues are repairable in a revision; none appears to be a fundamental flaw in the high-level approach. The paper is well-structured and the claimed results, if fixed, would be a strong contribution to streaming algorithms for clustering and subspace embeddings. I recommend requesting a revision rather than rejecting. No concerns about novelty or citation practice beyond the unproven Theorem 3.16 noted above."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nWhere 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.\n\nWho 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.","headline":"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.","tokens_in":44842,"tokens_out":4896,"would_cite":true,"duration_ms":48591,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68W20","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["streaming algorithms","(k,z)-clustering","coresets","subspace embeddings","Lewis weights","merge-and-reduce","sensitivity sampling","global encoding"],"falsifier":"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.","tokens_in":43634,"feed_emoji":"⚡","tokens_out":9334,"duration_ms":82185,"temperature":0.7,"pith_summary":"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.","feed_headline":"Streaming clustering now uses offline-level memory and update time","feed_subtitle":"For (k,z)-clustering and Lp embeddings, one pass now matches offline space and time, with memory independent of the stream length.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Supplies the near-optimal offline coreset construction whose size the streaming algorithm preserves; the space bound cites this construction.","marker":"[CLSS22]"},{"why":"Establishes the online-sensitivity sampling theorem and the previous o(log n)-space streaming result that the new algorithm improves.","marker":"[CWZ23]"},{"why":"Gives the optimal coreset size for (k,z)-clustering in the epsilon,z regime, setting the target space bound.","marker":"[HLW23]"},{"why":"Provides the inequality used to show that rounding offsets to powers of (1+epsilon') yields a strong coreset.","marker":"[SW18]"},{"why":"Local-search approximation used as the constant-factor solution in constrained-medoids sensitivity computations.","marker":"[GT08]"},{"why":"Fast k-means++ via rejection sampling; the paper generalizes its quadtree method to (k,z)-clustering for crude sensitivity approximations.","marker":"[CLN+20]"},{"why":"Online Lewis weight sampling with the sample bounds used for subspace embeddings in both p<=2 and p>2 regimes.","marker":"[WY23]"},{"why":"Defines Lewis weights and Lp sensitivities and gives the coreset sizes and sensitivity-to-Lewis relations used by the subspace embedding argument.","marker":"[CP15]"},{"why":"Constructs well-conditioned bases, used to precondition rows so rounding error can be charged to row sensitivities.","marker":"[DDH+09]"},{"why":"Gives the oblivious O(d/epsilon^2)-row subspace embedding used as the constant-factor embedding in the p=2 case.","marker":"[Sar06]"}],"fun_headline_variants":["Streaming clustering hits offline space and speed","One-pass clustering: memory and time now optimal","Streaming matches offline for clustering and embeddings","Fast streaming clustering with offline-level memory","Space-optimal streaming for clustering and Lp embeddings"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Streaming clustering hits offline space and speed","One-pass clustering: memory and time now optimal","Streaming matches offline for clustering and embeddings","Fast streaming clustering with offline-level memory","Space-optimal streaming for clustering and Lp embeddings"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000224,"raw_usage":{"total_tokens":1508,"prompt_tokens":1040,"completion_tokens":468,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":656,"completion_tokens_details":{"reasoning_tokens":400}},"tokens_in":656,"tokens_out":468,"duration_ms":4708,"temperature":1.0,"reasoning_tokens":400,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:10:08.411370+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}