Improved range minimum queries

DOI10.1016/J.JDA.2016.09.002zbMATH Open1409.68078OpenAlexW2532601525MaRDI QIDQ2397152FDOQ2397152

Gonzalo Navarro, Héctor Ferrada

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

Recommendations

• Practical range minimum queries revisited
• Range minimum queries in minimal space
• Compressed range minimum queries
• Compressed range minimum queries
• 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

zbMATH Keywords

range minimum querieslowest common ancestorscompact data structuresCartesian treesbalanced parentheses

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Succinct representation of balanced parentheses and static trees
• Fully functional static and dynamic succinct trees
• Recursive Star-Tree Parallel Data Structure
• Ultra-succinct representation of ordered trees with applications
• Title not available (Why is that?)
• Succinct Trees in Practice
• Representing trees of higher degree
• Compressed suffix trees with full functionality
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Succinct data structures for flexible text retrieval systems
• A unifying look at data structures
• Space-efficient data-analysis queries on grids
• Faster entropy-bounded compressed suffix trees
• Lempel-Ziv factorization using less time \& space
• A simple optimal representation for balanced parentheses

Cited In (8)

• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Property Suffix Array with Applications in Indexing Weighted Sequences
• Space-efficient data structure for next/previous larger/smaller value queries
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Range minimum queries in minimal space
• Lempel-Ziv compressed structures for document retrieval
• Title not available (Why is that?)

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)