Finding range minima in the middle: approximations and applications
From MaRDI portal
Publication:626956
DOI10.1007/s11786-009-0007-8zbMath1205.68493MaRDI 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 array; suffix tree; text indexing; succinct data structure; ballot number; range minimum query; Cartesian tree
68W05: Nonnumerical algorithms
68R05: Combinatorics in computer science
68W25: Approximation algorithms
Related Items
Unnamed Item, Simultaneous encodings for range and next/previous larger/smaller value queries, Linear-space data structures for range mode query in arrays, Encoding two-dimensional range top-\(k\) queries
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
