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