|
naistar (NAIST Academic Repository) >
学術リポジトリ naistar / NAIST Academic Repository naistar >
学術雑誌論文 / Journal Article >
情報科学研究科 / Graduate School of Information Science >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10061/6053
|
| Title: | Adaptive Bloom Filter: A space-efficient counting algorithm for unpredictable network traffic |
| Authors: | Matsumoto, Yoshihide
Hazeyama, Hiroaki
Kadobayashi, Youki |
| Issue Date: | 1-May-2008 |
| Publisher: | Institute of Electronics, Information and Communication Engineers |
| Journal Title: | IEICE transactions on information and systems |
| Volume: | E91-D |
| Issue: | 5 |
| Start page: | 1292 |
| End page: | 1299 |
| Abstract: | The Bloom Filter (BF), a space-and-time-efficient hashcoding 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 Zipfs distribution. Finally, we show that ABF can be used for an unpredictable data set such as real network traffic. |
| URI: | http://hdl.handle.net/10061/6053 |
| URL: | http://search.ieice.org |
| ISSN: | 0916-8532 |
| Rights: | Copyright (C)2008 IEICE |
| Text Version: | publisher |
| Publisher DOI: | 10.1093/ietisy/e91-d.5.1292 |
| Appears in Collections: | 情報科学研究科 / Graduate School of Information Science
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|
