On space efficient two dimensional range minimum data structures
From MaRDI portal
Publication:692632
DOI10.1007/s00453-011-9499-0zbMath1254.68093MaRDI 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
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
68P05: Data structures
Related Items
Unnamed Item, Two dimensional range minimum queries and Fibonacci lattices, Encoding 2D range maximum queries, The range 1 query (R1Q) problem, 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, On hardness of several string indexing problems, Succinct indices for path minimum, with applications, Time-space trade-offs for longest common extensions, Space efficient data structures for nearest larger neighbor, Succinct encodings for families of interval graphs, Encoding two-dimensional range top-\(k\) queries, Orthogonal Range Searching for Text Indexing, Array Range Queries, Fast String Dictionary Lookup with One Error, Range Minimum Query Indexes in Higher Dimensions, Space Efficient Data Structures for Nearest Larger Neighbor
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
