Optimal succinctness for range minimum queries
From MaRDI portal
Abstract: For a static array A of n ordered objects, a range minimum query asks for the position of the minimum between two specified array indices. We show how to preprocess A into a scheme of size 2n+o(n) bits that allows to answer range minimum queries on A in constant time. This space is asymptotically optimal in the important setting where access to A is not permitted after the preprocessing step. Our scheme can be computed in linear time, using only n + o(n) additional bits at construction time. In interesting by-product is that we also improve on LCA-computation in BPS- or DFUDS-encoded trees.
Recommendations
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Improved range minimum queries
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Practical range minimum queries revisited
- Finding range minima in the middle: approximations and applications
Cited in
(46)- On the minimum total length of interval systems expressing all intervals, and range-restricted queries
- The range 1 query (R1Q) problem
- LRM-trees: compressed indices, adaptive sorting, and compressed permutations
- Range minimum queries in minimal space
- Practical space-efficient index for structural pattern matching
- Reporting and counting maximal points in a query orthogonal rectangle
- Linear-space data structures for range mode query in arrays
- Improved range minimum queries
- Wavelet trees for all
- On reporting the \(L_1\) metric closest pair in a query rectangle
- Linear-space data structures for range frequency queries on arrays and trees
- Fully functional static and dynamic succinct trees
- On (dynamic) range minimum queries in external memory
- From time to space: fast algorithms that yield small and fast data structures
- Array range queries
- Lempel Ziv computation in small space (LZ-CISS)
- Space efficient data structures for nearest larger neighbor
- Self-indexing based on LZ77
- LRM-trees: compressed indices, adaptive sorting, and compressed permutations
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Data structures for efficient string algorithms.
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- On Cartesian Trees and Range Minimum Queries
- Colored range queries and document retrieval
- On compressing and indexing repetitive sequences
- Space-efficient data-analysis queries on grids
- On compressing permutations and adaptive sorting
- Improved algorithms for the range next value problem and applications
- Practical range minimum queries revisited
- Improved space-time tradeoffs for approximate full-text indexing with one edit error
- Efficient dynamic range minimum query
- A space-optimal grammar compression
- Succinct color searching in one dimension
- Inducing suffix and LCP arrays in external memory
- Space-efficient parallel construction of succinct representations of suffix tree topologies
- Combined data structure for previous- and next-smaller-values
- Top-\(k\) document retrieval in optimal time and linear space
- Finding range minima in the middle: approximations and applications
- Space-time trade-offs for the LCP array of Wheeler DFAs
- Computing all-vs-all MEMs in grammar-compressed text
- Hierarchical categories in colored searching
- Space efficient construction of Lyndon arrays in linear time
- On space efficient two dimensional range minimum data structures
- The ceBWT index: an index for circular Cartesian tree matching on multiple texts
- Extending the Burrows-Wheeler transform for Cartesian tree matching and constructing it
- Compact and succinct data structures for multidimensional orthogonal range searching
This page was built for publication: Optimal succinctness for range minimum queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557018)
