Tables should be sorted (on random access machines)
From MaRDI portal
Publication:5057459
DOI10.1007/3-540-60220-8_87zbMath1502.68117MaRDI QIDQ5057459
Peter Bro Miltersen, Faith E. Fich
Publication date: 16 December 2022
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-60220-8_87
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68P05: Data structures
68P20: Information storage and retrieval of data
Related Items
Nearly Optimal Static Las Vegas Succinct Dictionary, Optimal bounds for the predecessor problem and related problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Time bounded random access machines
- Storing a sparse table
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Self-adjusting binary search trees
- Should Tables Be Sorted?
- Implicit $O(1)$ Probe Search
- Membership in Constant Time and Almost-Minimum Space
- Nonoblivious hashing
- On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines