Optimal bounds for the predecessor problem and related problems
From MaRDI portal
Publication:1869935
DOI10.1006/jcss.2002.1822zbMath1020.68027OpenAlexW1986633843WikidataQ55889025 ScholiaQ55889025MaRDI QIDQ1869935
Publication date: 4 May 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/7dc5decedb24a0456c9e3ebcef8ed3c1428fbf25
Related Items
Dynamic nested brackets ⋮ The cell probe complexity of succinct data structures ⋮ Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations ⋮ Adjacency queries in dynamic sparse graphs ⋮ Alphabet-Dependent String Searching with Wexponential Search Trees ⋮ c-trie++: a dynamic trie tailored for fast prefix searches ⋮ Succinct encoding of arbitrary graphs ⋮ Algorithms in the Ultra-Wide Word Model ⋮ Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ Internal masked prefix sums and its connection to fully internal measurement queries ⋮ Improved bounds for finger search on a RAM ⋮ A uniform paradigm to succinctly encode various families of trees ⋮ Succinct Representations of Arbitrary Graphs ⋮ Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Fast local searches and updates in bounded universes ⋮ Towards optimal range medians ⋮ Two-dimensional packet classification and filter conflict resolution in the internet ⋮ Unnamed Item ⋮ Succinct data structures for searchable partial sums with optimal worst-case performance ⋮ Unnamed Item ⋮ A note on predecessor searching in the pointer machine model ⋮ Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings ⋮ Biased predecessor search ⋮ Dynamic interpolation search revisited ⋮ Minimal indices for predecessor search ⋮ Dynamic index and LZ factorization in compressed space ⋮ Unnamed Item ⋮ Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ A compressed dynamic self-index for highly repetitive text collections ⋮ Maximal common subsequence algorithms ⋮ A History of Distribution-Sensitive Data Structures ⋮ Linked dynamic tries with applications to LZ-compression in sublinear time and space
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dynamic fractional cascading
- A lower bound for finding predecessors in Yao's cell probe model
- Preserving order in a forest in less than logarithmic time and linear space
- Understanding the complexity of interpolation search
- Universal classes of hash functions
- On data structures and asymmetric communication complexity
- Fusion trees can be implemented with \(AC^0\) instructions only
- Surpassing the information theoretic bound with fusion trees
- STACS 98. 15th annual symposium on theoretical aspects of computer science. Paris, France, February 25--27, 1998. Proceedings
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Toward Optimal ϵ-Approximate Nearest Neighbor Algorithms
- Lower bounds for union-split-find related problems on random access machines
- A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
- Tight(er) worst-case bounds on dynamic searching and priority queues
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
- Hash functions for priority queues
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- A Lower Bound on the Complexity of the Union-Split-Find Problem
- Should Tables Be Sorted?
- Design and implementation of an efficient priority queue
- Dynamic Perfect Hashing: Upper and Lower Bounds
- A Reliable Randomized Algorithm for the Closest-Pair Problem
- Priority queues: Small, monotone and trans-dichotomous
- Predecessor queries in dynamic integer sets
- Tables should be sorted (on random access machines)
- Trans-dichotomous algorithms without multiplication — some upper and lower bounds
- Optimal static range reporting in one dimension
- Polynomial hash functions are reliable
- Efficient regular data structures and algorithms for dilation, location, and proximity problems
