HackerPapers

arXiv:1908.04810math.CO

On Occupancy Moments and Bloom Filter Efficiency

Jonathan Burns

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

Two multivariate committee distributions are shown to belong to Berg's family of factorial series distributions and Kemp's family of generalized hypergeometric factorial moment distributions. Exact moment formulas, upper and lower bounds, and statistical parameter estimators are provided for the classic occupancy and committee distributions. The derived moment equations are used to determine exact formulas for the false-positive rate and efficiency of Bloom filters -- probabilistic data structures used to solve the set membership problem. This study reveals that the conventional Bloom filter analysis overestimates the number of hash functions required to minimize the false-positive rate, and shows that Bloom filter efficiency is monotonic in the number of hash functions.

arXiv comments
Journal reference
DOI
Subjects
math.COCombinatorics cs.DSData Structures and Algorithms cs.ITInformation Theory math.PRProbability

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Jul 2020 to Jul 2020.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Bloom filters debunked: Dispelling 30 Years of bad math with Coq 1 comment

    • For Bloom filters specifically I preferred last year's "On Occupancy Moments and Bloom Filter Efficiency". You wouldn't guess from the title or abstract, but it's fairly comprehensive, including proofs of the expected false positive rates. https://arxiv.org/abs/1908.04810

      FreakLegionView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.