Reducing false positives of a bloom filter using cross-checking bloom filters

Hyesook Lim, Nara Lee, Jungwon Lee, Changhoon Yim

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

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.

Original languageEnglish
Pages (from-to)1865-1877
Number of pages13
JournalApplied Mathematics and Information Sciences
Volume8
Issue number4
DOIs
StatePublished - Jul 2014

Keywords

  • Algorithm
  • Bloom filter
  • Cross-checking bloom filters
  • False positive
  • Internet
  • Network
  • Router

Fingerprint

Dive into the research topics of 'Reducing false positives of a bloom filter using cross-checking bloom filters'. Together they form a unique fingerprint.

Cite this