A Space Lower Bound for Dynamic Approximate Membership Data Structures

DOI10.1137/120867044zbMath1285.68043OpenAlexW2146450895MaRDI QIDQ5408763

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

lower boundsdynamic data structuresbloom filters

Mathematics Subject Classification ID

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

Related Items (3)

Constructing SAT Filters with a Quantum Annealer ⋮ 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