On space efficient two dimensional range minimum data structures
From MaRDI portal
Publication:692632
DOI10.1007/s00453-011-9499-0zbMath1254.68093OpenAlexW2071469476MaRDI QIDQ692632
Gerth Stølting Brodal, S. Srinivasa Rao, Pooya Davoodi
Publication date: 6 December 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9499-0
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Related Items
Succinct indices for path minimum, with applications, Two dimensional range minimum queries and Fibonacci lattices, Space efficient data structures for nearest larger neighbor, The range 1 query (R1Q) problem, Succinct encodings for families of interval graphs, Encoding two-dimensional range top-\(k\) queries, Fast String Dictionary Lookup with One Error, Range Minimum Query Indexes in Higher Dimensions, Space Efficient Data Structures for Nearest Larger Neighbor, Encoding 2D range maximum queries, Time-space trade-offs for longest common extensions, The effective entropy of next/previous larger/smaller value queries, A simple linear-space data structure for constant-time range minimum query, Reporting and counting maximal points in a query orthogonal rectangle, Unnamed Item, Orthogonal Range Searching for Text Indexing, Array Range Queries, On hardness of several string indexing problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Replacing suffix trees with enhanced suffix arrays
- Succinct data structures for flexible text retrieval systems
- Lempel-Ziv factorization using less time \& space
- Dominance made simple
- Decomposable searching problems
- Dynamic orthogonal range queries in OLAP.
- The cell probe complexity of succinct data structures
- Compressed suffix trees with full functionality
- Optimal lower bounds for rank and select indexes
- Fast Algorithms for Finding Nearest Common Ancestors
- Space-Efficient Algorithms for Document Retrieval
- Two-Dimensional Range Minimum Queries
- An(other) Entropy-Bounded Compressed Suffix Tree
- Optimal Succinctness for Range Minimum Queries
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- On Cartesian Trees and Range Minimum Queries
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- A unifying look at data structures
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- Lowest common ancestors in trees and directed acyclic graphs
