On the false-positive rate of Bloom filters

DOI10.1016/J.IPL.2008.05.018zbMATH Open1191.68203DBLPjournals/ipl/BoseGKMMMST08OpenAlexW2167538128WikidataQ57009400 ScholiaQ57009400MaRDI QIDQ975449FDOQ975449

Authors Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Yihui Tang, Michiel Smid 

Publication date 9 June 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2008.05.018

zbMATH Keywords

analysis of algorithmsdata structuresrandomized data structure

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

Recommendations

• A new analysis of the false positive rate of a Bloom filter
• On the analysis of Bloom filters
• Network Applications of Bloom Filters: A Survey
• Cache-, hash-, and space-efficient bloom filters
• An optimal bloom filter replacement

Cites work

• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Compressed Bloom filters
• Exact and approximate membership testers
• Network Applications of Bloom Filters: A Survey
• Space/time trade-offs in hash coding with allowable errors
• Tail bounds for occupancy and the satisfiability threshold conjecture

Cited in

(15)

• An optimization problem related to Bloom filters with bit patterns
• Analysis of an algorithm catching elephants on the Internet
• Distance sensitive Bloom filters without false negatives
• Certifying certainty and uncertainty in approximate membership query structures
• Server-aided private set intersection based on reputation
• Supporting early pruning in top-\(k\) query processing on massive data
• Secure and efficient multiparty private set intersection cardinality
• Hiding the input-size in multi-party private set intersection
• Distance-Sensitive Bloom Filters
• A new analysis of the false positive rate of a Bloom filter
• Unconditionally secure multiparty computation for symmetric functions with low bottleneck complexity
• On the analysis of Bloom filters
• Bet-or-pass: adversarially robust Bloom filters
• Inferring insertion times and optimizing error penalties in time-decaying Bloom filters
• Network Applications of Bloom Filters: A Survey

This page was built for publication: On the false-positive rate of Bloom filters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q975449)