Less hashing, same performance: Building a better Bloom filter

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

Michael Mitzenmacher, Adam Kirsch

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 convergence; double hashing; bloom filters

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68M10: Network design and communication in computer systems

68P05: Data structures