Title: A New Algorithm for Accurate and Low-Space k-Median Clustering on Data Streams

Abstract: The k-median problem for insertion-only data streams is an active area of research.  In 2003, Charikar et al provided the first poly(k, log n)-space constant-approximation, albeit with a massive constant (~5500).  In the current work, we introduce a new technique that finds a low-constant approximation (~40) without requiring any additional storage.

Short Bio: Harry Lang is a doctoral student in the mathematics department at JHU.  He studies algebraic topology, and in particular computational methods for detecting topological structure of massive data sets.  In computer science, he works on streaming algorithms for clustering with Professor Vladimir Braverman.

This talk will be given remotely.