Optimal bounds for the predecessor problem and related problems
From MaRDI portal
Recommendations
Cites work
- A lower bound for finding predecessors in Yao's cell probe model
- A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
- A Lower Bound on the Complexity of the Union-Split-Find Problem
- A Reliable Randomized Algorithm for the Closest-Pair Problem
- Design and implementation of an efficient priority queue
- Dynamic fractional cascading
- Dynamic Perfect Hashing: Upper and Lower Bounds
- Efficient regular data structures and algorithms for dilation, location, and proximity problems
- Fusion trees can be implemented with AC^0 instructions only
- Hash functions for priority queues
- scientific article; zbMATH DE number 4101220 (Why is no real title available?)
- scientific article; zbMATH DE number 177800 (Why is no real title available?)
- scientific article; zbMATH DE number 1303597 (Why is no real title available?)
- scientific article; zbMATH DE number 1303598 (Why is no real title available?)
- scientific article; zbMATH DE number 1306898 (Why is no real title available?)
- scientific article; zbMATH DE number 512871 (Why is no real title available?)
- scientific article; zbMATH DE number 1528185 (Why is no real title available?)
- scientific article; zbMATH DE number 767429 (Why is no real title available?)
- scientific article; zbMATH DE number 1405797 (Why is no real title available?)
- scientific article; zbMATH DE number 1445338 (Why is no real title available?)
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Lower bounds for union-split-find related problems on random access machines
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- On data structures and asymmetric communication complexity
- Optimal static range reporting in one dimension
- Polynomial hash functions are reliable (extended abstract)
- Predecessor queries in dynamic integer sets
- Preserving order in a forest in less than logarithmic time and linear space
- Priority queues: small, monotone and trans-dichotomous
- Searching Unindexed and Nonuniformly Generated Files in \log \log N Time
- Should Tables Be Sorted?
- STACS 98. 15th annual symposium on theoretical aspects of computer science. Paris, France, February 25--27, 1998. Proceedings
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Surpassing the information theoretic bound with fusion trees
- Tables should be sorted (on random access machines)
- Tight(er) worst-case bounds on dynamic searching and priority queues
- Toward optimal -approximate nearest neighbor algorithms
- Trans-dichotomous algorithms without multiplication — some upper and lower bounds
- Understanding the complexity of interpolation search
- Universal classes of hash functions
Cited in
(44)- A lower bound for finding predecessors in Yao's cell probe model
- A simple optimal solution for the temporal precedence problem on pure pointer machines
- Dynamic nested brackets
- Improved bounds for finger search on a RAM
- Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings
- Two-dimensional packet classification and filter conflict resolution in the internet
- Dynamic interpolation search revisited
- Dynamic index and LZ factorization in compressed space
- Maximal common subsequence algorithms
- Linked dynamic tries with applications to LZ-compression in sublinear time and space
- The cell probe complexity of succinct data structures
- A uniform paradigm to succinctly encode various families of trees
- 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
- Minimal indices for predecessor search
- c-trie++: a dynamic trie tailored for fast prefix searches
- Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
- Optimal bounds for the predecessor problem
- A history of distribution-sensitive data structures
- The bit complexity of the predecessor problem
- The batched predecessor problem in external memory
- Time-space trade-offs for predecessor search
- Alphabet-dependent string searching with wexponential search trees
- Algorithms in the ultra-wide word model
- Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
- Succinct Representations of Arbitrary Graphs
- Succinct encoding of arbitrary graphs
- scientific article; zbMATH DE number 140457 (Why is no real title available?)
- scientific article; zbMATH DE number 1848393 (Why is no real title available?)
- An algorithm for finding predecessors in integer sets
- Optimal rank and select queries on dictionary-compressed text
- Conversion from RLBWT to LZ77
- Dynamic ordered sets with approximate queries, approximate heaps and soft heaps
- scientific article; zbMATH DE number 7250167 (Why is no real title available?)
- Towards optimal range medians
- Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees
- Internal masked prefix sums and its connection to fully internal measurement queries
- Predecessor on the Ultra-Wide Word RAM
- Fast local searches and updates in bounded universes
- Efficient algorithms for enumerating maximal common subsequences of two strings
- Succinct data structures for searchable partial sums with optimal worst-case performance
- A compressed dynamic self-index for highly repetitive text collections
- Adjacency queries in dynamic sparse graphs
- A note on predecessor searching in the pointer machine model
This page was built for publication: Optimal bounds for the predecessor problem and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1869935)
