Login New user?  
01-Applied Mathematics & Information Sciences
An International Journal
               
 
 
 
 
 
 
 
 
 
 
 
 
 

Content
 

Volumes > Volume 08 > No. 4

 
   

Reducing False Positives of a Bloom Filter using Cross-Checking Bloom Filters

PP: 1865-1877
Author(s)
Hyesook Lim, Nara Lee, Jungwon Lee, Changhoon Yim,
Abstract
A Bloom filter is a compact data structure that supports membership queries on a set, allowing false positives. The simplicity and the excellent performance of a Bloom filter make it a standard data structure of great use in many network applications. In reducing the false positive rate of a Bloom filter, it is well known that the size of a Bloom filter and accordingly the number of hash indices should be increased. In this paper, we propose a new architecture reducing the false positive rate of a Bloom filter more efficiently. The proposed architecture uses cross-checking Bloom filters that are queried in case of positives of a main Bloom filter to cross-check the results. If every cross-checking Bloom filters produce negatives, the positive of the main Bloom filter can be determined as a false positive. The main Bloom filter is not necessarily large to reduce the false positive rate, since more numbers of the false positives of the main Bloom filter are identified by cross-checking Bloom filters. Simulation results show that the false positive of the proposed scheme converges to zero faster, while requiring the total memory size for Bloom filters smaller, than that of a single Bloom filter architecture.

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved