|
|
|
|
|
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. |
|
|
|
|
|