Elastic Bloom Filter: Deletable and ExpandableFilter Using Elastic Fingerprints

Yuhan Wu (1) , Jintao He (1) , Shen Yan (1) , Jianyu Wu (1) , Tong Yang (1, 2) , Olivier Ruas (3) , Gong Zhang (4) , Bin Cui (1)

1 Peking University [Beijing]
2 Pengcheng Laboratory = Peng Cheng Laboratory [Shenzhen]
3 SPIRALS - Self-adaptation for distributed services and large software systems
4 Huawei Technologies [Shenzhen]

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.

Mots clés: Bloom filter; Elastic Bloom filter; Elastic Fingerprints; Bloom filter expansion

Domaines: Apprentissage [cs.LG]; Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Base de données [cs.DB]

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⟩