2015/11/29 by Artem Barger, Barger, Artem, Dan Feldman +1
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1511.08990
openalex publication_date 2015/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ω(d)=Ω(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.