1 PAPER Adaptive Bloom Filter: A Space-Efficient Counting Algorithm for Unpredictable Network Traffic

efficient hash-coding method, is used as one of the fundamen-tal modules in several network processing algorithms and appli-cations such as route lookups, cache hits, packet classification, per-flow state management or network monitoring. BF is a sim-ple space-efficient randomized data structure used to represent a data set in order to support membership queries. However, BF generates false positives, and cannot count the number of distinct elements. A counting Bloom Filter (CBF) can count the num-ber of distinct elements, but CBF needs more space than BF. We propose an alternative data structure of CBF, and we called this structure an Adaptive Bloom Filter (ABF). Although ABF uses the same-sized bit-vector used in BF, the number of hash functions employed by ABF is dynamically changed to record the number of appearances of a each key element. Consider-ing the hash collisions, the multiplicity of a each key element on ABF can be estimated from the number of hash functions used to decode the membership of the each key element. Although ABF can realize the same functionality as CBF, ABF requires the same memory size as BF. We describe the construction of ABF and IABF (Improved ABF), and provide a mathematical analysis and simulation using Zipf ’s distribution. Finally, we show that ABF can be used for an unpredictable data set such as real network traffic. key words: Bloom Filter, counting, burst traffic 1