k-Means for Streaming and Distributed Big Sparse Data

By Artem Barger, Dan Feldman. 2015

32 citations recorded by the source corpus.

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 $\mathbb{R}^d$, where each vector has $O(1)$ non-zeroes entries, and $d\geq 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\cdot k^{O(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\cdot k^{O(1)}$ (sparse) input points between the machines. % Our main technical result is a deterministic algorithm for computing a sparse $(k,\epsilon)$-coreset, which is a weighted subset of $k^{O(1)}$ input points that approximates the sum of squared distances from the $n$ input points to every $k$ centers, up to $(1\pm\epsilon)$ factor, for any given constant $\epsilon>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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

The Power of the Hybrid Model for Mean Estimation (2018, methodology): “Other DP K-means algorithms exist in both the TCM [4, 8, 43, 46, 48, 53] and LM [47, 52, 54, 57] which improve on our two non-hybrid K-means algorithms.”
Training Gaussian Mixture Models at Scale via Coresets (2017, background): “, whose size is independent of λ, and (ii) of size independent of d, as in Barger and Feldman (2016).”
Core‐sets: An updated survey (2019, methodology): “…random constructions whose output is polynomial in d replaced them (Chen, 2009), and independency of d is sometimes possible using either weak coresets (Feldman & Tassa, 2015) or squared Euclidean distances (Barger & Feldman, 2016; Feldman, Ozer, & Rus, 2017; Feldman, Schmidt, & Sohler, 2013).”