A new Bloom filter structure for identifying true positiveness of a Bloom filter

Ju Hyoung Mun, Jungwon Lee, Hyesook Lim

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

Bloom filters have been employed in various fields because of its simple and effective structure in identifying the membership of an input. Since a Bloom filter can produce false positives, the positive results of a Bloom filter should be identified whether the positives are true or not by accessing the original database. A complement Bloom filter (C-BF) was introduced to identify the true positiveness of a given Bloom filter without accessing the original database. A critical problem of the C-BF is that every element included in the complement set of the given set should be programmed into the C-BF. Since the number of elements included in the complement set can be considerably large, the C-BF would require the significant amount of memory. In this paper, we claim that the elements that produce negative results from the given Bloom filter are not necessarily programmed into the C-BF, since Bloom filters never produce false negatives. In other words, we propose the Petit-BF (P-BF) which programs only the elements that cause false positives from the given Bloom filter. Simulation results and theoretical analysis show that the proposed method can achieve the same performance using a considerably smaller amount of memory.

Original languageEnglish
Title of host publicationHPSR 2017 - 2017 IEEE 18th International Conference on High Performance Switching and Routing
PublisherIEEE Computer Society
ISBN (Electronic)9781509028399
DOIs
StatePublished - 5 Jul 2017
Event18th IEEE International Conference on High Performance Switching and Routing, HPSR 2017 - Campinas, Brazil
Duration: 18 Jun 201721 Jun 2017

Publication series

NameIEEE International Conference on High Performance Switching and Routing, HPSR
Volume2017-June
ISSN (Print)2325-5595
ISSN (Electronic)2325-5609

Conference

Conference18th IEEE International Conference on High Performance Switching and Routing, HPSR 2017
Country/TerritoryBrazil
CityCampinas
Period18/06/1721/06/17

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

Fingerprint

Dive into the research topics of 'A new Bloom filter structure for identifying true positiveness of a Bloom filter'. Together they form a unique fingerprint.

Cite this