Streaming Euclidean k-median and k-means with o(log n) Space
summary
Presents a streaming algorithm that breaks the long standing Omega(log(n Delta)) word barrier for insertion-only Euclidean (k,z)-clustering by producing a (1+epsilon)-approximate coreset at all times using ~O(dk/epsilon^2 2^{z log z} min(1/epsilon^z,k) poly(log log(n Delta))) words, combines online sensitivity sampling with a quadtree/EMD style embedding, L1 sketching and sparse recovery, and handles k-means by duplicating points near cell boundaries; also proves a single-pass dynamic lower bound of Omega(log^2 n) and gives a two-pass dynamic algorithm using o(log n) words*.
AI-written summary · about
chapters (11)
- 0:00Introduction to clustering
- 3:27Streaming model overview
- 7:12Coreset concepts
- 10:18Merge and reduce framework
- 14:08Sensitivity sampling
- 20:08Online sensitivity algorithm
- 27:20Algorithm questions and K
- 34:47Dynamic stream challenges
- 38:21Quadtree embeddings
- 43:48Dynamic algorithm construction
- 52:55Conclusion and Q&A
related talks
42mk-means and k-medians under Dimension Reduction
35mClustering: A Guide for the Perplexed
28mCertified Sub-Linear Lower Bounds for K-Means Clustering
46mRecent Advances in Diversity Maximization in the Offline and Composable Coreset Models
34mSubspace Clustering using Ensembles of K-Subspaces
33mOnline Multiserver Convex Chasing and Optimization
37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
42mRobust Mixture Learning when Outliers Overwhelm Small Groups