The Veracious
Counting Bloom Filter
Brindha Palanisamy1 and
Senthilkumar Athappan2
1Research Scholar, Anna
University, India
2Department of
Electrical and Electronics Engineering, Anna University, India
Abstract: Counting Bloom Filters (CBFs) are widely employed in many
applications for fast membership queries. CBF works on dynamic sets rather than
a static set via item insertions and deletions. CBF allows false positive, but
not false negative. The Bh-Counting Bloom Filter (Bh-CBF)
and Variable Increment Counting Bloom Filter (VI-CBF) are introduced to reduce
the False Positive Probability (FPP), but they suffer from memory overhead and
hardware complexity. In this paper, we proposed a multilevel optimization
approach named as Veracious Bh-Counting Bloom Filter (VBh-CBF)
and Veracious Variable Increment Counting Bloom Filter (VVI-CBF) by
partitioning the counter vector into multiple levels to reduce the FPP and to
limit the memory requirement. The experiment result shows that the FPP and
total memory size are reduced by 65.4%, 67.74% and 20.26%, 41.29%
respectively compared
to basic Bh-CBF and VI-CBF.
Key words: Bloom filter, false positive, counting bloom filter, intrusion detection system.
Received
August 3, 2014; accepted November 25, 2015