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
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;
Conference_Titel :
Computer Engineering and Technology (ICCET), 2010 2nd International Conference on
Conference_Location :
Chengdu
Print_ISBN :
978-1-4244-6347-3
DOI :
10.1109/ICCET.2010.5485832
