The search functionality is under construction.
The search functionality is under construction.

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

Yoshihide MATSUMOTO, Hiroaki HAZEYAMA, Youki KADOBAYASHI

  • Full Text Views

    5

  • Cite this

Summary :

The Bloom Filter (BF), a space-and-time-efficient hash-coding method, is used as one of the fundamental modules in several network processing algorithms and applications such as route lookups, cache hits, packet classification, per-flow state management or network monitoring. BF is a simple 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 number 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. Considering 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.

Publication
IEICE TRANSACTIONS on Information Vol.E91-D No.5 pp.1292-1299
Publication Date
2008/05/01
Publicized
Online ISSN
1745-1361
DOI
10.1093/ietisy/e91-d.5.1292
Type of Manuscript
Special Section PAPER (Special Section on Information and Communication System Security)
Category
Network Security

Authors

Keyword