Loading...
Please wait, while we are loading the content...
Similar Documents
1 paper adaptive bloom filter: a space-efficient counting algorithm for unpredictable network traffic.
| Content Provider | CiteSeerX |
|---|---|
| Abstract | 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. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Space-efficient Counting Algorithm Key Element Paper Adaptive Bloom Filter Unpredictable Network Traffic Hash Function Distinct Element Alternative Data Structure Memory Size Network Monitoring Counting Bloom Filter Fundamen-tal Module Cannot Count Several Network Unpredictable Data Set Cache Hit Data Structure Adaptive Bloom Filter Efficient Hash-coding Method Mathematical Analysis Same-sized Bit-vector Membership Query Packet Classification Route Lookup Zipf Distribution Real Network Traffic False Positive Improved Abf Per-flow State Management Bloom Filter Key Word Data Set Hash Collision Burst Traffic |
| Content Type | Text |
