Skip to Main content Skip to Navigation
New interface
Journal articles

Elastic Bloom Filter: Deletable and ExpandableFilter Using Elastic Fingerprints

Abstract : The Bloom filter, answering whether an item is in a set, has achieved great success in various fields, including networking, databases, and bioinformatics. However, the Bloom filter has two main shortcomings: no support of item deletion and no support of expansion. Existing solutions either support deletion at the cost of using additional memory, or support expansion at the cost of increasing the false positive rate and decreasing the query speed. Unlike existing solutions, we propose the Elastic Bloom filter (EBF) to address the two shortcomings simultaneously. Importantly, when EBF expands, the false positives decrease. Our key technique is Elastic Fingerprints, which dynamically absorb and release bits during compression and expansion. To support deletion, EBF can first delete the corresponding fingerprint and then update the corresponding bit in the Bloom filter. To support expansion, Elastic Fingerprints release bits and insert them to the Bloom filter. Our experimental results show that the Elastic Bloom filter significantly outperforms existing works.
Complete list of metadata

https://hal.inria.fr/hal-03347690
Contributor : Olivier Ruas Connect in order to contact the contributor
Submitted on : Friday, September 17, 2021 - 2:05:03 PM
Last modification on : Tuesday, December 6, 2022 - 12:42:13 PM
Long-term archiving on: : Saturday, December 18, 2021 - 6:48:26 PM

File

ElasticBloomFilter.pdf
Files produced by the author(s)

Identifiers

Citation

Yuhan Wu, Jintao He, Shen Yan, Jianyu Wu, Tong Yang, et al.. Elastic Bloom Filter: Deletable and ExpandableFilter Using Elastic Fingerprints. IEEE Transactions on Computers, 2021, pp.1-1. ⟨10.1109/TC.2021.3067713⟩. ⟨hal-03347690⟩

Share

Metrics

Record views

27

Files downloads

209