Streaming Algorithms for Heavy Hitters

Thursday, May 11, 2017 - 11:00am EDT

Speaker: Muthu Muthukrishnan, Rutgers University


Say we have items i and their frequencies f(i), with total frequency over all times being F, and the total number of items being n.  An item i is a heavy hitter if f(i) >= k F, for some constant fraction k, like 1/100. The problem we study is how to identify these heavy hitters when the items are presented not in an array, but as a continual stream of observations, and we have small space, say much less than n. The heavy hitter problem underlies many data analyses such as finding trends in data mining, identifying attacks in IP networks, and compressed sensing in signal processing. This problem has been studied extensively in the past few decades.
     In this talk, I will present an overview of classical algorithms and present new directions that have recently emerged such as heavy hitters in high dimensional streams using graphical models from Statistics and Machine Learning, heavy hitters in Software Defined Networking with memory stages, and others.


Muthu Muthukrishnan is a Distinguished Professor in the Department of Computer Science at Rutgers University, New Brunswick, NJ. His research interest is in algorithmic theory and its applications. His recent work is on applications like streaming systems, online advertising auctions, software defined networking and others. He is an ACM Fellow.