# k-Means for Streaming and Distributed Big Sparse Data

arXiv: https://arxiv.org/abs/1511.08990 · HTML: https://mlsanity.com/paper/1511.08990/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2015.

## Built on by (most cited first, 3 of 3)

- [Communication-efficient k-Means for Edge-based Machine Learning](https://mlsanity.com/paper/2102.04282/) (2021)
- [Composable Core-sets for Diversity Approximation on Multi-Dataset Streams](https://mlsanity.com/paper/2308.05878/) (2023)
- [Scalable and Distributed Silhouette Approximation](https://mlsanity.com/paper/2607.01993/) (2026)

## Abstract (arXiv)

We provide the first streaming algorithm for computing a provable approximation to the k-means of sparse Big data. Here, sparse Big Data is a set of n vectors in ℝd, where each vector has O(1) non-zeroes entries, and d≥ n. E.g., adjacency matrix of a graph, web-links, social network, document-terms, or image-features matrices. Our streaming algorithm stores at most log n· kO(1) input points in memory. If the stream is distributed among M machines, the running time reduces by a factor of M, while communicating a total of M· kO(1) (sparse) input points between the machines. % Our main technical result is a deterministic algorithm for computing a sparse (k,ε)-coreset, which is a weighted subset of kO(1) input points that approximates the sum of squared distances from the n input points to every k centers, up to (1±ε) factor, for any given constant ε>0. This is the first such coreset of size independent of both d and n. Existing algorithms use coresets of size at least polynomial in d, or project the input points on a subspace which diminishes their sparsity, thus require memory and communication Omega(d)=Omega(n) even for k=2. Experimental results real public datasets shows that our algorithm boost the performance of such given heuristics even in the off-line setting. Open code is provided for reproducibility.