Aarhus University Seal / Aarhus Universitets segl

Theory Seminar: Jelani Nelson - BPTree: an l_2 heavy hitters algorithm using constant memory

In the 'frequent items' problem one sees a sequence of items in a stream (e.g. a stream of words coming into a search query engine like Google) and wants to report a small list of items containing all frequent items. We would like algorithms for this problem that use memory substantially sublinear in the length of the stream.

2019.03.19 | Dorthe Haagen Nielsen

Date Wed 20 Mar
Time 14:15 15:00
Location Nygaard-295 (5335-295), Åbogade 34, 8200 Aarhus N

In this talk we describe a new state-of-the-art solution to this problem, called the "BPTree". We make use of chaining methods to control the suprema of Rademacher processes to develop this new algorithm which has provably near-optimal memory consumption for the "l_2" heavy hitters problem, improving upon the CountSieve and CountSketch from previous work.

Based on joint work with Vladimir Braverman, Stephen Chestnut, Nikita Ivkin, Zhengyu Wang, and David P. Woodruff


Jelani Nelson is an Associate Professor of Computer Science and John L. Loeb Associate Professor of Engineering and Applied Sciences at Harvard University. Nelson is interested in big data and the development of efficient algorithms. He joined the computer science faculty at Harvard University in 2013 and has remained there since. He is known for his contributions to streaming algorithms and dimensionality reduction, including proving that the Johnson-Lindenstrauss lemma is optimal (with Kasper Green Larsen), developing the Sparse Johnson-Lindenstrauss Transform (with Daniel Kane), and an asymptotically optimal algorithm for the count-distinct problem (with Daniel Kane and David P. Woodruff).e holds two patents related to applications of streaming algorithms to network traffic monitoring applications.

Host: Kasper Green Larsen

Site Specific, Lecture / talk, CS frontpage, MADALGO , Public/media, Staff, Students, Alumni