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 language | English |
|---|---|
| Article number | 9121313 |
| Pages (from-to) | 2123-2127 |
| Number of pages | 5 |
| Journal | IEEE Communications Letters |
| Volume | 24 |
| Issue number | 10 |
| DOIs | |
| State | Published - 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: [email protected]).
Publisher Copyright:
© 1997-2012 IEEE.
Keywords
- Bloom filter
- functional Bloom filter
- key-value data structure
- search failure