DocumentCode :
1940380
Title :
One memory access bloom filters and their generalization
Author :
Qiao, Yan ; Li, Tao ; Chen, Shigang
Author_Institution :
Dept. of Comput. & Inf. Sci. & Eng., Univ. of Florida, Gainesville, FL, USA
fYear :
2011
fDate :
10-15 April 2011
Firstpage :
1745
Lastpage :
1753
Abstract :
The Bloom filters have been extensively applied in many network functions. Their performance is judged by three criteria: processing overhead, space overhead, and false positive ratio. Due to wide applicability, any improvement to the performance of Bloom filters can potentially have broad impact in many areas of networking research. In this paper, we propose Bloom-1, a new data structure that performs membership check in one memory access, which compares favorably with the k memory accesses of a classical Bloom filter. We also generalize Bloom-1 to Bloom-g, allowing performance tradeoff between membership query overhead and false positive ratio. We thoroughly examine the variants in this new family of filters, and show that they can be configured to outperform the Bloom filters with a smaller number of memory accesses, a smaller or equal number of hash bits, and a smaller and comparable false positive ratio in practical scenarios. We also perform experiments based on a real traffic trace to support our new filter design.
Keywords :
computer network security; cryptography; filtering theory; telecommunication traffic; Bloom filter; Bloom-1; Bloom-g; data structure; false positive ratio; filter design; hash bit; membership check; membership query overhead; memory access; network function; networking research; processing overhead; real traffic trace; space overhead; Arrays; Hardware; Information filters; Memory management; Random access memory; Throughput;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
INFOCOM, 2011 Proceedings IEEE
Conference_Location :
Shanghai
ISSN :
0743-166X
Print_ISBN :
978-1-4244-9919-9
Type :
conf
DOI :
10.1109/INFCOM.2011.5934972
Filename :
5934972
Link To Document :
بازگشت