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

2025/04/22 by Vincent Cohen-Addad, Cohen-Addad, Vincent, L. Wang +5
Computer Science · #Advanced Clustering Algorithms Research #Data Structures and Algorithms (cs.DS) #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #Face and Expression Recognition

paper · pdf · doi:10.48550/arxiv.2504.16229

openalex publication_date 2025/04/22 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28

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 Δ, yielding an optimal bound of O(\fracdkmin(ε⁴,ε^z+2)) words for accuracy parameter ε on d-dimensional points. Additionally, we obtain amortized update time of d log(k)\cdotpolylog(log(nΔ)), which is an exponential improvement over the previous d poly(k,log(nΔ)). 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 O(d) update time and space-optimal constructions, using O((d²)/(ε²)) words for p≤ 2 and O(\fracd^p/2+1ε²) words for p>2, showing that streaming algorithms can match offline algorithms in both space and time complexity.

Citations

• Fully Dynamic k-Median with Near-Optimal Update Time and Recourse
• Fully Dynamic k-Clustering with Fast Update Time and Small Recourse
• Faster and Simpler Greedy Algorithm for k-Median and k-Means
• Fully Dynamic k-Means Coreset in Near-Optimal Update Time
• Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
• Near-Optimal k-Clustering in the Sliding Window Model
• Streaming Euclidean k-median and k-means with o(log n) Space
• On Optimal Coreset Construction for Euclidean (k,z)-Clustering
• Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
• Near-Linear Sample Complexity for L_p Polynomial Regression
• Online Lewis Weight Sampling
• Adaptive Sketches for Robust Regression with Importance Sampling
• Fast Regression for Structured Inputs
• Towards Optimal Lower Bounds for k-median and k-means Coresets
• Active Linear Regression for ℓ_p Norms and Beyond
• L1 Regression with Lewis Weights Subsampling
• Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence
• Fast and Accurate k-means++ via Rejection Sampling
• Fully-Dynamic Coresets
• Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal
• Tight Bounds for the Subspace Sketch Problem with Applications
• Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
• Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension
• Near Optimal Linear Algebra in the Online and Sliding Window Models
• Online Row Sampling
• Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
• Sketching as a Tool for Numerical Linear Algebra
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• A Unified Framework for Approximating and Clustering Data
• A unified framework for approximating and clustering data
• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• Simpler Analyses of Local Search Algorithms for Facility Location
• Sampling Algorithms and Coresets for Lp Regression
• Fully Dynamic k-Clustering in O(k) Update Time
• Improved Coresets for Euclidean k-Means

Related

• Streaming Euclidean k-median and k-means with o(log n) Space
• Asymptotically exact streaming algorithms
• Streaming Balanced Clustering
• Nearly Optimal Dynamic k-Means Clustering for High-Dimensional Data
• Clustering High Dimensional Dynamic Data Streams