Finding range minima in the middle: approximations and applications
From MaRDI portal
Publication:626956
DOI10.1007/s11786-009-0007-8zbMath1205.68493OpenAlexW2088521838MaRDI QIDQ626956
Publication date: 19 February 2011
Published in: Mathematics in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11786-009-0007-8
suffix arraysuffix treetext indexingsuccinct data structureballot numberrange minimum queryCartesian tree
Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Approximation algorithms (68W25)
Related Items
Simultaneous encodings for range and next/previous larger/smaller value queries ⋮ Encoding two-dimensional range top-\(k\) queries ⋮ Linear-space data structures for range mode query in arrays ⋮ Unnamed Item
Cites Work
- 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
- Super ballot numbers
- Waiting patterns for a printer
- Compressed suffix trees with full functionality
- Constructing suffix arrays in linear time
- Compressed representations of sequences and full-text indexes
- An analysis of the Burrows—Wheeler transform
- Suffix Arrays on Words
- An(other) Entropy-Bounded Compressed Suffix Tree
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- A unifying look at data structures
- Recursive Star-Tree Parallel Data Structure
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- String Processing and Information Retrieval
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Lowest common ancestors in trees and directed acyclic graphs
- Combinatorial Pattern Matching
This page was built for publication: Finding range minima in the middle: approximations and applications
