NAISTAR
Advanced Search
Japanese | English

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

Files in This Item:

File Description SizeFormat
IEICE_E91-D_5_1292.pdf341.29 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Copyright (c) 2007-2012 Nara Institute of Science and Technology All Rights Reserved.
DSpace Software Copyright © 2002-2010  Duraspace - Feedback