Time-space trade-offs for predecessor search

DOI10.1145/1132516.1132551zbMath1301.68150arXivcs/0603043OpenAlexW2095681182MaRDI QIDQ2931388

Mihai Pǎtraşcu, Mikkel Thorup

Publication date: 25 November 2014

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

Full work available at URL: https://arxiv.org/abs/cs/0603043

zbMATH Keywords

lower boundspredecessor searchcell-probe complexity

Mathematics Subject Classification ID

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

Related Items (39)

Optimal encodings for range majority queries ⋮ I/O-efficient 2-d orthogonal range skyline and attrition priority queues ⋮ Longest common extensions in trees ⋮ Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search ⋮ Nearly Optimal Static Las Vegas Succinct Dictionary ⋮ Longest Common Extensions in Trees ⋮ Efficient range searching for categorical and plain data ⋮ Entropy-bounded representation of point grids ⋮ Space-efficient data-analysis queries on grids ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The nearest colored node in a tree ⋮ Unnamed Item ⋮ Block trees ⋮ Optimal indexes for sparse bit vectors ⋮ Universal compressed text indexing ⋮ Approximate query processing over static sets and sliding windows ⋮ Compressed data structures: Dictionaries and data-aware measures ⋮ Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os ⋮ Substring Range Reporting ⋮ Substring range reporting ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Unnamed Item ⋮ A note on predecessor searching in the pointer machine model ⋮ Biased predecessor search ⋮ Efficient and compact representations of some non-canonical prefix-free codes ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Dynamic interpolation search revisited ⋮ Minimal indices for predecessor search ⋮ Unnamed Item ⋮ Hashed Patricia Trie: Efficient Longest Prefix Matching in Peer-to-Peer Systems ⋮ Unnamed Item ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Unnamed Item ⋮ LZ-End Parsing in Linear Time ⋮ Faster compressed quadtrees ⋮ Succinct Color Searching in One Dimension ⋮ Adaptive succinctness

This page was built for publication: Time-space trade-offs for predecessor search