DocumentCode :
518197
Title :
A variable length counting Bloom filter
Author :
Li, Lichun ; Wang, Bingqiang ; Lan, Julong
Author_Institution :
Nat. Digital Switching Syst. Eng. & Technol. R&D Center, Inf. Eng. Univ., Zhenzhou, China
Volume :
3
fYear :
2010
fDate :
16-18 April 2010
Abstract :
In this paper, a new data structure called variable length counting Bloom filter is proposed for membership queries. This data structure uses variable length counters instead of fixed length counters in Bloom filter. Rules for the operations of the filter are defined. The size of the new data structure is analyzed. Both the analysis and the simulation show that it is about 1.7 times of that of the standard Bloom filter, which is much less than that of the traditional counting Bloom filter. The application range of the new filter is as wide as the counting Bloom filter.
Keywords :
counters; data structures; Bloom filter; data structure; membership queries; variable length counter; Costs; Counting circuits; Data engineering; Data structures; Digital filters; Information filtering; Information filters; Research and development; Switching systems; Systems engineering and theory; Bloom filter; hash function; membership query; variable length;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Engineering and Technology (ICCET), 2010 2nd International Conference on
Conference_Location :
Chengdu
Print_ISBN :
978-1-4244-6347-3
Type :
conf
DOI :
10.1109/ICCET.2010.5485832
Filename :
5485832
Link To Document :
بازگشت