Saturday Morning Video: New Algorithms for Heavy Hitters in Data Streams, David Woodruff at IHP

IHP just organized a series of talks within what they call the nexus trimester which had a focus on  Inference Problems -the whole playlist is here-. Here are a few presentations related to the theme of Nuit Blanche.

New Algorithms for Heavy Hitters in Data Streams, David Woodruff

Abstract: An old and fundamental problem in databases and data streams is that of finding the heavy hitters, also known as the top-k, most popular items, frequent items, elephants, or iceberg queries. There are several variants of this problem, which quantify what it means for an item to be frequent, including what are known as the ℓ1-heavy hitters and ℓ2-heavy hitters. There are a number of algorithmic solutions for these problems, starting with the work of Misra and Gries, as well as the CountMin and CountSketch data structures, among others. In this talk we cover several recent results developed in this area, which improve upon the classical solutions to these problems. In particular, we develop new algorithms for finding ℓ1-heavy hitters and ℓ2-heavy hitters, with significantly less memory required than what was known, and which are optimal in a number of parameter regimes.
Based on recent works with Arnab Bhattacharyya, Palash Dey and Vladimir Braverman, Stephen Chestnut, Nikita Ivkin

 

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.