A lower bound for finding predecessors in Yao's cell probe model

DOI10.1007/BF02126797zbMath0659.68030OpenAlexW1985177045MaRDI QIDQ1112590

Miklós Ajtai

Publication date: 1988

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02126797

zbMATH Keywords

data structurecell probe model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items (11)

Online timestamped text indexing ⋮ The cell probe complexity of succinct data structures ⋮ Lower bounds for dynamic algorithms ⋮ An algorithm for finding predecessors in integer sets ⋮ Optimal collapsing protocol for multiparty pointer jumping ⋮ On the cell probe complexity of polynomial evaluation ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Cell-probe lower bounds for the partial match problem ⋮ On data structures and asymmetric communication complexity ⋮ Succinct Color Searching in One Dimension ⋮ Optimal bounds for the predecessor problem and related problems

Cites Work

• Log-logarithmic worst-case range queries are possible in space theta(N)
• Hash functions for priority queues
• Should Tables Be Sorted?

This page was built for publication: A lower bound for finding predecessors in Yao's cell probe model