[Theory Seminar] Harry Lang

September 2, 2015 @ 12:00 pm – 1:00 pm


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.