Performance Evaluation and Comparison of Four Counting Bloom Filter Schemes
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    The Counting Bloom Filter (CBF) is a space-efficient data structure that extends a Bloom filter so as to allow approximate multiplicity queries on a dynamic multi-set. An in-depth study of three existing CBF schemes is presented, that is, the Na?ve Counting Bloom Filter (NCBF), the Space-Code Bloom Filter (SCBF) and the d-left Counting Bloom Filter (dlCBF). Then, a CBF scheme called Binary Shrinking d-left Counting Bloom Filter (BSdlCBF) is proposed. A performance metrics named load adaptability for CBF schemes is also defined. The performance of the four CBF schemes is evaluated by using metrics of counting error, space complexity and load adaptability under both uniform and Zipfian multiplicity distributions. The experimental results show that the proposed BSdlCBF outperforms the other three in terms of accuracy, space-efficiency and load adaptability. The cost of such an advantage of BSdlCBF is a reasonable rise in computational and space complexity.

    Reference
    Related
    Cited by
Get Citation

张 进,邬江兴,刘勤让.4 种计数型Bloom Filter 的性能分析与比较.软件学报,2010,21(5):1098-1114

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 18,2008
  • Revised:October 27,2008
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063