Exact and approximate membership testers

DOI10.1145/800133.804332MaRDI QIDQ5402541zbMATH OpenOpenAlexFDO

Authors L. Carter, Robert W. Floyd, John Gill, George Markowsky, Mark N. Wegman

Publication date 14 March 2014

Published in Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800133.804332

Mathematics Subject Classification ID

Information theory (general) (94A15) Nonnumerical algorithms (68W05)

Recommendations

• Membership in Constant Time and Almost-Minimum Space
• Set membership with a few bit probes
• Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
• Are Bitvectors Optimal?
• Set membership with non-adaptive bit probes

Cited in

(11)

• scientific article; zbMATH DE number 1389362 (Why is no real title available?)
• Dynamic dictionaries for multisets and counting filters with constant time operations
• Support optimality and adaptive cuckoo filters
• On the false-positive rate of Bloom filters
• Testing membership in parenthesis languages
• New hash functions and their use in authentication and set equality
• Bet-or-pass: adversarially robust Bloom filters
• Fast Evaluation of Union-Intersection Expressions
• Tight bounds for sliding Bloom filters
• Fast scalable construction of ([compressed] static | minimal perfect hash) functions
• Dynamic dictionaries for multisets and counting filters with constant time operations

This page was built for publication: Exact and approximate membership testers

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