Improved range minimum queries

DOI10.1016/J.JDA.2016.09.002MaRDI QIDQ2397152zbMATH OpenOpenAlexFDO

Authors Héctor Ferrada, Gonzalo Navarro

Publication date 29 May 2017

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2016.09.002

zbMATH Keywords

range minimum querieslowest common ancestorscompact data structuresCartesian treesbalanced parentheses

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Practical range minimum queries revisited
• Range minimum queries in minimal space
• Improved range searching lower bounds
• Range minimum query indexes in higher dimensions
• Optimal succinctness for range minimum queries
• Efficient dynamic range minimum query
• I/O-efficient range minima queries
• Lower bound for succinct range minimum query

Cites work

• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• A simple optimal representation for balanced parentheses
• A unifying look at data structures
• Compressed suffix trees with full functionality
• Faster entropy-bounded compressed suffix trees
• Fully functional static and dynamic succinct trees
• Lempel-Ziv factorization using less time \& space
• Recursive Star-Tree Parallel Data Structure
• Representing trees of higher degree
• Space-efficient data-analysis queries on grids
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct Trees in Practice
• Succinct data structures for flexible text retrieval systems
• Succinct representation of balanced parentheses and static trees
• Ultra-succinct representation of ordered trees with applications

Cited in

(15)

• Space-efficient data structure for next/previous larger/smaller value queries
• Range minimum queries in minimal space
• Succinct representations of binary trees for range minimum queries
• Property Suffix Array with Applications in Indexing Weighted Sequences
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Lempel-Ziv compressed structures for document retrieval
• Dualities in tree representations
• On Cartesian trees and range minimum queries
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Efficient dynamic range minimum query
• Optimal succinctness for range minimum queries
• Practical range minimum queries revisited
• How to answer a small batch of RMQs or LCA queries in practice
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.

This page was built for publication: Improved range minimum queries

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