Asymmetric Sparse Bloom Filter

MyungKeun YOON  JinWoo SON  Seon-Ho SHIN  

IEICE TRANSACTIONS on Communications   Vol.E97-B   No.4   pp.765-772
Publication Date: 2014/04/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E97.B.765
Type of Manuscript: PAPER
Category: Internet
Bloom filter,  membership testing,  string matching,  virus scanning,  

Full Text: PDF(951.6KB)>>
Buy this Article

We propose a new Bloom filter that efficiently filters out non-members. With extra bits assigned and asymmetrically distributed, the new filter reduces hash computations and memory accesses. For an error rate of 10-6, the new filter reduces cost by 31.31% with 4.33% additional space, while the standard method saves offers a 20.42% reduction.