Optimal bounds for the predecessor problem

DOI10.1145/301250.301323MaRDI QIDQ2819557zbMATH OpenOpenAlexFDO

Authors Paul Beame, Faith E. Fich

Publication date 29 September 2016

Published in Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Optimal bounds for the predecessor problem and related problems
• Time-space trade-offs for predecessor search
• A lower bound for finding predecessors in Yao's cell probe model
• Lower bounds for predecessor searching in the cell probe model
• An algorithm for finding predecessors in integer sets

Cited in

(13)

• A lower bound for finding predecessors in Yao's cell probe model
• Optimal bounds for the predecessor problem and related problems
• Compressed data structures: Dictionaries and data-aware measures
• Minimal indices for predecessor search
• The bit complexity of the predecessor problem
• The batched predecessor problem in external memory
• Time-space trade-offs for predecessor search
• scientific article; zbMATH DE number 1848393 (Why is no real title available?)
• An algorithm for finding predecessors in integer sets
• LZ-End Parsing in Linear Time
• Succinct color searching in one dimension
• Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
• A note on predecessor searching in the pointer machine model

This page was built for publication: Optimal bounds for the predecessor problem

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