Hierarchical Heavy Hitters with the Space Saving Algorithm

Details Hierarchical Heavy Hitters with the Space Saving Algorithm Hierarchical Heavy Hitters with the Space Saving Algorithm

2011-02-27

arxiv.org/abs/1102.5540v2

Computer Science

Data Structures and Algorithms

22 pages, 18 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Hierarchical Heavy Hitters with the Space Saving Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hierarchical Heavy Hitters with the Space Saving Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical Heavy Hitters with the Space Saving Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-54224