The limits of buffering: a tight lower bound for dynamic membership in the external memory model

DOI10.1145/1806689.1806752MaRDI QIDQ2875172zbMATH OpenOpenAlexFDO

Authors Elad Verbin, Qin Zhang

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

data structuresexternal memorymembership

Mathematics Subject Classification ID

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

Recommendations

• The limits of buffering: a tight lower bound for dynamic membership in the external memory model
• scientific article; zbMATH DE number 2079384
• On the cell probe complexity of dynamic membership
• scientific article; zbMATH DE number 6297800
• Logarithmic Lower Bounds in the Cell-Probe Model

Cited in

(8)

• Threshold data structures and coding theory
• The limits of buffering: a tight lower bound for dynamic membership in the external memory model
• scientific article; zbMATH DE number 2079384 (Why is no real title available?)
• Cache-oblivious hashing
• Hierarchical bin buffering
• On the cell probe complexity of dynamic membership
• On the I/O complexity of dynamic distinct counting
• Using hashing to solve the dictionary problem

This page was built for publication: The limits of buffering: a tight lower bound for dynamic membership in the external memory model

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