Kenjiro Cho is Research Director at Internet Initiative Japan, Inc. He is also a board member of the WIDE project. He received the B.S. degree in electronic engineering from Kobe University, the M.Eng. degree in computer science from Cornell University, and the Ph.D. degree in media and governance from Keio University. His current research interests include Internet measurement and data analysis, and cloud networking.
Hierarchical Heavy Hitters: Why and How?
Finding frequent items (Heavy Hitters) in a large dataset has diverse applications and has been extensively studied. Items with hierarchical attributes such as IP addresses or time can be aggregated into groups such as subnets or coarser time. Identifying these frequent aggregates, known as Hierarchical Heavy Hitters, provides powerful means for traffic monitoring or anomaly detection.
In this talk, I will review the existing algorithms for Heavy Hitter and Hierarchical Heavy Hitter problems, and then, introduce an efficient algorithm based on recursive space partitioning. I'll also introduce a traffic monitoring tool based on the proposed method that has been used for monitoring the WIDE backbone traffic.