IEEE Transactions on Computers · 2021 · 44 citations · 33 references
ComputingBioinformaticsComputer ScienceData StructuresDatabasesInformation RetrievalData CompressionQuery ExpansionQuery ProcessingBloom FiltersExpansionFalse Positive Rate Reduction
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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Elastic Fingerprints</i> , 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.
33
Space/time trade-offs in hash coding with allowable errors
Burton H. Bloom · Communications of the ACM · 1970 · 7.5K citations · Full text
Network traffic characteristics of data centers in the wild
Theophilus Benson, Aditya Akella, David A. Maltz · 2010 · 2.2K citations
3D-Stacked Memory Architectures for Multi-core Processors
Gabriel H. Loh · 2008 · 436 citations
Deep packet inspection using parallel Bloom filters
Sarang Dharmapurikar, Praveen Thaggikuppe Krishnamurthy, Todd Sproull et al. · 2004 · 301 citations