Hierarchical Heavy Hitters with the Space Saving Algorithm

Michael Mitzenmacher, Thomas Steinke, Justin Thaler

Abstract: The Hierarchical Heavy Hitters problem extends the notion of frequent items to data arranged in a hierarchy. This problem has applications to network traffic monitoring, anomaly detection, and DDoS detection. We present a new streaming approximation algorithm for computing Hierarchical Heavy Hitters that has several advantages over previous algorithms. It improves on the worst-case time and space bounds of earlier algorithms, is conceptually simple and substantially easier to implement, offers improved accuracy guarantees, is easily adopted to a distributed or parallel setting, and can be efficiently implemented in commodity hardware such as ternary content addressable memory (TCAMs). We present experimental results showing that for parameters of primary practical interest, our two-dimensional algorithm is superior to existing algorithms in terms of speed and accuracy, and competitive in terms of space, while our one-dimensional algorithm is also superior in terms of speed and accuracy for a more limited range of parameters.

Published: ALENEX12
Conference Version: [pdf]
Full Version: [on arXiv]
Source Code and Data: [zip] (Please read the runme file.)
Extra Graphs: [zip]
Slides: [pdf] (Presented at ALENEX12, Kyoto, Japan, January 2012)
Bibtex:  
@inproceedings{MitzenmacherSteinkeThaler2012,
   author = {Michael Mitzenmacher and Thomas Steinke and Justin Thaler},
   title = {Hierarchical Heavy Hitters with the Space Saving Algorithm},
   booktitle = {Proceedings of the Meeting on Algorithm Engineering and Experiments},
   series = {ALENEX '12},
   year = {2012},
   isbn = {978-1-611972-12-2},
   location = {Kyoto, Japan},
   pages = {160--174},
   numpages = {15},
   url = {http://siam.omnibooksonline.com/2012ALENEX/data/papers/027.pdf},
   publisher = {SIAM},
   address = {3600 Market Street, 6th Floor, Philadelphia, PA 19104-2688 USA},
}
 

Last updated on 1 March 2012 by Thomas Steinke.