A space lower bound for dynamic approximate membership data structures

DOI10.1137/120867044MaRDI QIDQ5408763zbMATH OpenOpenAlexFDO

Authors Shachar Lovett, Ely Porat

Publication date 11 April 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://escholarship.org/uc/item/8sm8m910

zbMATH Keywords

bloom filtersdynamic data structureslower bounds

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• An optimal bloom filter replacement
• Approximate range emptiness in constant time and optimal space
• Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
• Tight bounds for sliding Bloom filters
• scientific article; zbMATH DE number 6469129

Cited in

(5)

• Constructing SAT filters with a quantum annealer
• Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)
• Approximate range emptiness in constant time and optimal space
• Bloom filter encryption and applications to efficient forward-secret 0-RTT key exchange
• Tight bounds for sliding Bloom filters

This page was built for publication: A space lower bound for dynamic approximate membership data structures

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