Less hashing, same performance: Building a better Bloom filter

DOI10.1002/rsa.20208zbMath1156.68368OpenAlexW4243961364MaRDI QIDQ3522836

Adam Kirsch, Michael Mitzenmacher

Publication date: 4 September 2008

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.2442

zbMATH Keywords

Poisson convergencedouble hashingbloom filters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Network design and communication in computer systems (68M10) Data structures (68P05)

Related Items (6)

An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters ⋮ Efficient and robust associative memory from a generalized Bloom filter ⋮ On the analysis of Bloom filters ⋮ Layered hashing algorithm for real-time systems ⋮ An index-split Bloom filter for deep packet inspection ⋮ Load Thresholds for Cuckoo Hashing with Double Hashing

Cites Work

• More analysis of double hashing
• Compressed bloom filters
• Network Applications of Bloom Filters: A Survey
• Balls and bins: A study in negative dependence
• Model Checking Software
• Less Hashing, Same Performance: Building a Better Bloom Filter
• Probability and Computing
• Formal Methods in Computer-Aided Design
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Less hashing, same performance: Building a better Bloom filter