Pay For A Sliding Bloom Filter And Get Counting, Distinct Elements, And Entropy For Free

Authors:
Eran Assaf Hebrew University, Israel
Ran Ben Basat Technion, Israel
Gil Einziger Nokia Bell labs, Israel
Roy Friedman Technion, Israel

Abstract:

For many networking applications, recent data is more significant than older data, motivating the need for sliding window solutions. Various capabilities, such as DDoS detection and load balancing, require insights about multiple metrics including Bloom filters, per-flow counting, count distinct and entropy estimation. In this work, we present a unified construction that solves all the above problems in the sliding window model. Our single solution offers a better space to accuracy tradeoff than the state-of-the-art for each of these individual problems! We show this both analytically and by running multiple real Internet backbone and datacenter packet traces.

You may want to know: