Time-space trade-offs for predecessor search
From MaRDI portal
Publication:2931388
DOI10.1145/1132516.1132551zbMath1301.68150arXivcs/0603043OpenAlexW2095681182MaRDI QIDQ2931388
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
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
