Reproduce “countBF: A General-purpose High Accuracy and Space Efficient Counting Bloom Filter” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Sabuzima Nayak, Ripon Patgiri
A novel counting Bloom Filter, `countBF`, significantly lowers false positive probability to an average of 0.000013 and reduces memory footprint by up to 7.85 times compared to conventional counting Bloom Filters. This structure offers high accuracy (99.999921% average) and supports dynamic item deletion without compromising insertion or lookup speeds.
Key insights
- Packing multiple small counters into larger 64-bit integer cells, combined with specific bitwise operations, allows for efficient counting and a reduced memory footprint.
- A 2D array structure with prime number dimensions and a modified hashing strategy effectively distributes items, leading to fewer hash collisions and substantially lower false positive rates.
- Balancing the number of bits per counter within the 64-bit cells is crucial for optimizing both operational performance (insertion/lookup speed) and memory efficiency.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.