On the false-positive rate of Bloom filters

DOI10.1016/j.ipl.2008.05.018zbMath1191.68203OpenAlexW2167538128WikidataQ57009400 ScholiaQ57009400MaRDI QIDQ975449

Pat Morin, Prosenjit Bose, Jason Morrison, Anil Maheshwari, Evangelos Kranakis, Hua Guo, Yihui Tang, Michiel H. M. 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)

Related Items

A new analysis of the false positive rate of a Bloom filter ⋮ On the analysis of Bloom filters ⋮ Hiding the input-size in multi-party private set intersection ⋮ Supporting early pruning in top-\(k\) query processing on massive data ⋮ Secure and efficient multiparty private set intersection cardinality ⋮ Server-aided private set intersection based on reputation

Cites Work

• Unnamed Item
• Unnamed Item
• Compressed bloom filters
• Network Applications of Bloom Filters: A Survey
• Tail bounds for occupancy and the satisfiability threshold conjecture
• Exact and approximate membership testers
• Space/time trade-offs in hash coding with allowable errors