Streaming Euclidean K-Median and K-Means With O-Log N Space

Explore a lecture on streaming algorithms for Euclidean k-median and k-means clustering that achieves groundbreaking space efficiency. Delve into the innovative approach presented by Samson Zhou from Texas A&M University, which breaks the long-standing Omega(log(n Delta)) memory barrier. Learn about the novel algorithm that provides a (1+epsilon)-approximation for the more general (k,z)-clustering problem using only ~O(dk/varepsilon^2)*(2^{z log z})*min(1/epsilon^z, k)*poly(log log(n Delta)) words of memory. Discover the implications of this advancement for data stream clustering and its potential impact on various techniques such as coresets, merge-and-reduce framework, bicriteria approximation, and sensitivity sampling. Gain insights into the collaborative work with Vincent Cohen-Addad and David P. Woodruff, which pushes the boundaries of space-efficient clustering algorithms.

Streaming Euclidean k-median and k-means with o(log n) Space