Exact and approximate membership testers

DOI10.1145/800133.804332zbMATH Open1282.68191OpenAlexW2018423671MaRDI QIDQ5402541FDOQ5402541

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

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

Mathematics Subject Classification ID

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

Cited In (11)

• Dynamic dictionaries for multisets and counting filters with constant time operations
• Support optimality and adaptive cuckoo filters
• Testing membership in parenthesis languages
• On the false-positive rate of Bloom filters
• 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
• Dynamic dictionaries for multisets and counting filters with constant time operations
• Fast scalable construction of ([compressed] static | minimal perfect hash) functions
• Title not available (Why is that?)

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)