Complement bloom filter for identifying true positiveness of a bloom filter

Hyesook Lim, Jungwon Lee, Changhoon Yim

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

The use of Bloom filters in network applications has increased rapidly. Since Bloom filters can produce false positives, the trueness of each positive needs to be identified by referring to an off-chip hash table. This letter proposes a new method for identifying the trueness of Bloom filter positives. We propose the use of an additional Bloom filter programmed for the complement set of the given set. In querying an input, if the complement Bloom filter produces a negative result, the input is a member of the given set since Bloom filters never produce a false negative. When both Bloom filters produce positives, a hash table needs to be referred to in our method. We provide a mathematical analysis, whereby the probability of referring to a hash table converges to the summation of the false positive probabilities of each Bloom filter. We provide the simulation result that the rate of referring to a hash table in our method is the order of 10-5 for Bloom filter sizing factor 32.

Original languageEnglish
Article number2478462
Pages (from-to)1905-1908
Number of pages4
JournalIEEE Communications Letters
Volume19
Issue number11
DOIs
StatePublished - 1 Nov 2015

Keywords

  • Bloom filter
  • complement Bloom filter
  • false positive
  • negative
  • true positive

Fingerprint

Dive into the research topics of 'Complement bloom filter for identifying true positiveness of a bloom filter'. Together they form a unique fingerprint.

Cite this