Addition of a Secondary Functional Bloom Filter

Hayoung Byun, Sohyun Kim, Changhoon Yim, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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
Volume24
Issue number10
DOIs
StatePublished - Oct 2020

Bibliographical note

Funding Information:
Manuscript received May 26, 2020; accepted June 15, 2020. Date of publication June 19, 2020; date of current version October 9, 2020. This work was supported by the National Research Foundation of Korea (NRF) grants funded by the Korea government (MIST): NRF-2019R1H1A2079873 and NRF-2020R1A2C1004071. The associate editor coordinating the review of this letter and approving it for publication was E. Bastug. (Corresponding author: Hyesook Lim.) Hayoung Byun, Sohyun Kim, and Hyesook Lim are with the Department of Electronic and Electrical Engineering, Ewha Womans University, Seoul 03760, South Korea (e-mail: hlim@ewha.ac.kr).

Publisher Copyright:
© 1997-2012 IEEE.

Keywords

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

Fingerprint

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

Cite this