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

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

zbMATH Keywords

analysis of algorithmsdata structuresrandomized data structure

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Space/time trade-offs in hash coding with allowable errors
• Title not available (Why is that?)
• Network Applications of Bloom Filters: A Survey
• Tail bounds for occupancy and the satisfiability threshold conjecture
• Compressed Bloom filters
• Exact and approximate membership testers

Cited In (16)

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

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)