Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

Simons Institute via YouTube

Overview

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.

Syllabus

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

Taught by

Simons Institute

Reviews

Start your review of Streaming Euclidean K-Median and K-Means With O-Log N Space

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.