Addition of a Secondary Functional Bloom Filter

Hayoung Byun, Sohyun Kim, Changhoon Yim, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Key-value data structures have been extensively used in various applications. When a large amount of data needs to be compactly stored in a fixed memory size, a functional Bloom filter is a space-efficient key-value structure. In this letter, we propose a 2-stage functional Bloom filter structure composed of a primary functional Bloom filter and a secondary functional Bloom filter to resolve the indeterminables produced from the primary functional Bloom filter. We analytically present the memory ratio allocated for each of the two Bloom filters to achieve the lowest search failure rate. The analytical result is validated through experiments, thereby demonstrating that the optimal performance is realized when the secondary functional Bloom filter uses 3% of the total memory.

Original languageEnglish
Article number9121313
Pages (from-to)2123-2127
Number of pages5
JournalIEEE Communications Letters
Issue number10
StatePublished - Oct 2020


  • Bloom filter
  • functional Bloom filter
  • key-value data structure
  • search failure


Dive into the research topics of 'Addition of a Secondary Functional Bloom Filter'. Together they form a unique fingerprint.

Cite this