TY - JOUR
T1 - A dynamic structure of counting bloom filter
AU - Gu, Jianhua
AU - Zhou, Xingshe
PY - 2012
Y1 - 2012
N2 - Counting Bloom Filter based on the counter-array structure has the shortcoming of counter overflow and less space-efficient. To address these shortcomings, we propose a dynamic structure for Counting Bloom Filter which dynamically changes the counter size according to the number of inserted elements. Hence it not only makes a better use of memory space but also eliminates counter overflow. We put up with the methods of addition and subtraction bit by bit while inserting and deleting elements to effectively reduce the times of memory access. In this way, an effective tradeoff can be achieved between counter access speed and space efficiency. Besides, to reduce excessive memory allocation/deallocation cost caused by consecutively changing counter size, we propose a configurable delayed shrinking algorithm which can appropriately delay the counter size shrinking based on user's configuration. The experiment results show that our dynamic structure could meet the needs of most application scenarios.
AB - Counting Bloom Filter based on the counter-array structure has the shortcoming of counter overflow and less space-efficient. To address these shortcomings, we propose a dynamic structure for Counting Bloom Filter which dynamically changes the counter size according to the number of inserted elements. Hence it not only makes a better use of memory space but also eliminates counter overflow. We put up with the methods of addition and subtraction bit by bit while inserting and deleting elements to effectively reduce the times of memory access. In this way, an effective tradeoff can be achieved between counter access speed and space efficiency. Besides, to reduce excessive memory allocation/deallocation cost caused by consecutively changing counter size, we propose a configurable delayed shrinking algorithm which can appropriately delay the counter size shrinking based on user's configuration. The experiment results show that our dynamic structure could meet the needs of most application scenarios.
UR - http://www.scopus.com/inward/record.url?scp=84862884377&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-28308-6_5
DO - 10.1007/978-3-642-28308-6_5
M3 - 会议文章
AN - SCOPUS:84862884377
SN - 1867-5662
VL - 145 AISC
SP - 31
EP - 37
JO - Advances in Intelligent and Soft Computing
JF - Advances in Intelligent and Soft Computing
IS - VOL. 2
T2 - 2011 2nd International Congress on Computer Applications and Computational Science, CACS 2011
Y2 - 15 November 2011 through 17 November 2011
ER -