Practical range minimum queries revisited

DOI10.4230/LIPICS.SEA.2017.12MaRDI QIDQ4580157zbMATH OpenOpenAlexFDO

Authors Niklas Baumstark, Simon Gog, Tobias Heuer, Julian Labeit

Publication date 13 August 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.SEA.2017.12

zbMATH Keywords

algorithm engineeringrange minimum queriessuccinct data structures

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Improved range minimum queries
• Optimal succinctness for range minimum queries
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

Cited in

(14)

• On the minimum total length of interval systems expressing all intervals, and range-restricted queries
• How to answer a small batch of RMQs or LCA queries in practice
• Range minimum queries in minimal space
• Improved range minimum queries
• Two Dimensional Range Minimum Queries and Fibonacci Lattices
• The Range 1 Query (R1Q) Problem
• Range median of minima queries, super-Cartesian trees, and text indexing
• Two-Dimensional Range Minimum Queries
• 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
• Property Suffix Array with Applications in Indexing Weighted Sequences
• A simple representation of tree covering utilizing balanced parentheses and efficient implementation of average-case optimal RMQs
• FL-RMQ: a learned approach to range minimum queries

This page was built for publication: Practical range minimum queries revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580157)