Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou · 2025
Read Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings by Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16229.txt.
Introduction
Vincent Cohen-Addad and co-authors show that streaming data tools can match their offline peers. In streaming, data flow past once and memory is tight. Two core jobs are grouping points into clusters and shrinking data while keeping its shape. Past stream methods lagged on space or speed against offline ones.
Their algorithms close that gap on both fronts. Memory for clustering no longer grows with the count of points or their spread. Update time drops sharply as well. For shape keeping sketches, they hit the best known space bounds with fast updates. The clustering method is also the fastest known even offline, a rare double win.
Catalog record
| CREATOR | Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 162 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-16229
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou 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 ) (k,z) -clustering in the streaming model, we achieve a number of words of memory which is independent of the number n n of input points and the aspect ratio Δ \Delta , yielding an optimal bound of 𝒪 ~ ( d k min ( ε 4 , ε z + 2 ) ) \tilde{\mathcal{O}}\left(\frac{dk}{\min(\varepsilon^{4},\varepsilon^{z+2})}\right) words for accuracy parameter ε \varepsilon on d d -dimensional points. Additionally, we obtain amortized update time of d log ( k ) ⋅ polylog ( log ( n Δ ) ) d\,\log(k)\cdot\text{polylog}(\log(n\Delta)) , which is an exponential improvement over the previous d poly ( k , log ( n Δ ) ) d\,\text{poly}(k,\log(n\Delta)) . Our method also gives the fastest runtime for ( k , z ) (k,z) -clustering even in the offline setting. For subspace embeddings in the streaming model, we achieve 𝒪 ( d ) \mathcal{O}(d) update time and space-optimal constructions, using 𝒪 ~ ( d 2 ε 2 ) \tilde{\mathcal{O}}\left(\frac{d^{2}}{\varepsilon^{2}}\right) words for p ≤ 2 p\leq 2 and 𝒪 ~ ( d p / 2 + 1 ε 2 ) \tilde{\mathcal{O}}\left(\frac{d^{p/2+1}}{\varepsilon^{2}}\right) words for p > 2 p>2 , showing that streaming algorithms can match offline algorithms in both space and time complexity. 1 Introduction The streaming model of computation is a powerful framework for processing large-scale datasets that are too vast to be stored in memory. In the streaming setting, algorithms must quickly make decisions based on a sequence of updates that are irrevocably discarded after processing, without the possibility of revisiting past data. The primary challenge is to design algorithms that can efficiently approximate, compute, or detect properties of the underlying dataset, while ensuring both fast update time and using memory that is sublinear in both the dataset size and the length of the data stream. This model is well-suited for applications in data summarization, where the goal is to extract meaningful insights from large, evolving datasets. Such applications include clustering, which is widely applied in domains such as customer segmentation, anomaly detection in network traffic, and pattern recognition in sensor networks, as well as subspace embeddings, which reduce dimensionality in areas including image processing, recommendation systems, and natural language processing. Despite significant progress, it remained open whether such fundamental tasks inherently require more space or time in the streaming model compared to their offline counterparts. Clustering and data streams. Clustering is a fundamental problem that seeks to partition a dataset so that similarly structured points are grouped together and differently structured points are separated. Variations of clustering are used across a wide range of applications, including bioinformatics, combinatorial optimization, computational geometry, computer graphics, data science, and machine learning. In the Euclidean (k,z) -clustering problem, the input is a set X of n points x_{1},\ldots,x_{n}\in\mathbb{R}^{d} , a cluster parameter k>0 , and a positive integer exponent z>0 , and the goal is to minimize the clustering cost across all sets {\mathcal{C}} of at most k centers: \min_{{\mathcal{C}}\subset\mathbb{R}^{d},|{\mathcal{C}}|\leq k}\Cost(X,{\mathcal{C}}):=\min_{{\mathcal{C}}\subset\mathbb{R}^{d},|{\mathcal{C}}|\leq k}\sum_{i=1}^{n}\min_{c\in{\mathcal{C}}}\|x_{i}-c\|_{2}^{z}.\vskip-3.61371pt For z=1 and z=2 , respectively, the (k,z) -clustering problem corresponds to the well-known k -median and k -means clustering problems. For clustering in the standard insertion-only streaming model, the points x_{1},\ldots,x_{n} of X arrive sequentially along with an input accuracy parameter \varepsilon>0 . The goal is for each time t\in[n] to find a clustering {\mathcal{C}}_{t} on the prefix X_{t} of the first t points of X with cost that is a (1+\varepsilon) -multiplicative approximation of the optimal clustering of X_{t} . To that end, note that a set {\mathcal{C}} of k centers implicitly defines the overall clustering, since each point is assigned to the closest cluster center. In fact, it is not feasible to directly output a label for every point in X using space sublinear in n=|X| , and so in some sense, outputting {\mathcal{C}} is the most reasonable objective we can hope for. We also remark that due to bit representation, input points cannot be represented in arbitrary precision and thus we generally rescale the points in X to lie within the grid \{1,\ldots,\Delta\}^{d} . Subspace embeddings and data streams. Subspace embeddings are a fundamental tool in dimensionality reduction, enabling the preservation of algebraic and geometric structure, while significantly reducing data dimensionality. The problem has been extensively studied, with applications spanning theoretical computer science, machine learning, randomized linear algebra, scientific computing, and data science. In the subspace embedding problem, the input is once again a set A of n points x_{1},\ldots,x_{n}\in\mathbb{R}^{d} , which induces a matrix {\mathbf{A}}\in\mathbb{R}^{n\times d} , where typically n\gg d . Given an accuracy parameter \varepsilon>0 , the goal is to construct a matrix {\mathbf{M}} such that for all vectors {\mathbf{x}}\in\mathbb{R}^{d} , (1-\varepsilon)\|{\mathbf{M}}{\mathbf{x}}\|_{p}\leq\|{\mathbf{A}}{\mathbf{x}}\|_{p}\leq(1+\varepsilon)\|{\mathbf{A}}{\mathbf{x}}\|_{p}, where \|\cdot\|_{p} denotes the L_{p} norm of a vector. In the standard insertion-only streaming model, the rows of {\mathbf{A}} arrive sequentially and at each time t\in[n] , the goal is to find a subspace embedding for the matrix {\mathbf{A}}_{t} consisting of the first t rows of {\mathbf{A}} . Streaming algorithms and coresets. The most common approach for both fast and space-efficient streaming algorithms for data summarization problems such as (k,z) -clustering and subspace embeddings is to collect a small weighted subset of the points from the input dataset. For clustering, this forms a (strong) coreset Z_{t} at time t , which is a data structure that preserves the clustering cost for any choice {\mathcal{C}} of k centers, i.e., \Cost(X_{t},{\mathcal{C}})\approx\Cost(Z_{t},{\mathcal{C}}) . We can then perform an efficient (k,z) -clustering algorithm on each coreset Z_{t} to identify an optimal or near-optimal set of cluster centers. For subspace embeddings, this forms a coreset {\mathbf{M}}_{t} at time t , from which we can approximately extract \|{\mathbf{A}}_{t}{\mathbf{x}}\|_{2} for any {\mathbf{x}}\in\mathbb{R}^{d} , i.e., \|{\mathbf{M}}_{t}{\mathbf{x}}\|_{2}\approx\|{\mathbf{A}}_{t}{\mathbf{x}}\|_{2} . Naturally, smaller coreset constructions correspond to both faster and more space-efficient algorithms. In the offline setting where the input dataset X is given upfront and there are no space restrictions, there exist coreset constructions for both clustering and subspace embeddings that sample a number of weighted points that is independent of the size of the input. For (k,z) -clustering, there exist coreset constructions [ CSS21 , CLSS22 , HLW23 , CLS+22 ] that sample \tilde{\mathcal{O}}\left(\min\left(\frac{1}{\varepsilon^{2}}\cdot k^{2-\frac{z}{z+2}},\frac{1}{\min(\varepsilon^{4},\varepsilon^{2+z})}\cdot k\right)\right) weighted points of X 1 1 1 Note that the bound is actually \tilde{\mathcal{O}}\left(\min\left(\frac{k^{3/2}}{\varepsilon^{2}},\frac{k}{\min(\varepsilon^{4},\varepsilon^{2+z})}\right)\right) for k -means and \tilde{\mathcal{O}}\left(\min\left(\frac{k^{4/3}}{\varepsilon^{2}},\frac{k}{\min(\varepsilon^{4},\varepsilon^{2+z})}\right)\right) for k -median. , where we use \tilde{\mathcal{O}}\left(f\right) for a function f to denote f\cdot\polylog(f) . Similarly for subspace embeddings, there exist coreset constructions that sample \tilde{\mathcal{O}}\left(\frac{d}{\varepsilon^{2}}\right) weighted rows of {\mathbf{A}} [ DMM06a , DMM06b , Mag10 , Woo14 ] . These coreset constructions have size that is independent of the size n of the input dataset, which is especially important as modern datasets often consist of hundreds of millions of points. On the other hand, despite a long line of work on clustering in the streaming model [ HM04 , HK07 , Che09 , FL11 , BFLR19 , CWZ23 , WZZ23 ]