Addition of a Secondary Functional Bloom Filter
- 주제(키워드) Bloom filter , functional Bloom filter , key-value data structure , search failure
- 등재 SCIE, SCOPUS
- 발행기관 Institute of Electrical and Electronics Engineers Inc.
- 발행년도 2020
- 총서유형 Journal
- URI http://www.dcollection.net/handler/ewha/000000174754
- 본문언어 영어
- Published As http://dx.doi.org/10.1109/LCOMM.2020.3003695
초록/요약
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. © 1997-2012 IEEE.
more