Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
From MaRDI portal
Publication:3020013
DOI10.1137/090779759zbMath1222.05024OpenAlexW2007791040WikidataQ56501371 ScholiaQ56501371MaRDI QIDQ3020013
Publication date: 29 July 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/ce421e1de7596da0d9a6972d3df43648d26c6a2a
Trees (05C05) Combinatorics in computer science (68R05) Data structures (68P05) Algorithms on strings (68W32)
Related Items
Optimal encodings for range majority queries ⋮ Compressed string dictionary search with edit distance one ⋮ Succinct indices for path minimum, with applications ⋮ On succinct representations of binary trees ⋮ Document retrieval with one wildcard ⋮ New variants of perfect non-crossing matchings ⋮ Two dimensional range minimum queries and Fibonacci lattices ⋮ Longest common extensions in trees ⋮ Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max ⋮ Space-efficient indexes for forbidden extension queries ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Space efficient data structures for nearest larger neighbor ⋮ The heaviest induced ancestors problem: better data structures and applications ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ Simultaneous encodings for range and next/previous larger/smaller value queries ⋮ Improved range minimum queries ⋮ The range 1 query (R1Q) problem ⋮ Succinct encodings for families of interval graphs ⋮ Parallel construction of succinct trees ⋮ Longest Common Extensions in Trees ⋮ Range Minimum Query Indexes in Higher Dimensions ⋮ Encodings of Range Maximum-Sum Segment Queries and Applications ⋮ Encoding Nearest Larger Values ⋮ Compressed property suffix trees ⋮ Compact binary relation representations with rich functionality ⋮ Compressed dynamic range majority and minority data structures ⋮ Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance ⋮ Entropy-bounded representation of point grids ⋮ An Opportunistic Text Indexing Structure Based on Run Length Encoding ⋮ Longest common substring with approximately \(k\) mismatches ⋮ Internal shortest absent word queries in constant time and linear space ⋮ Multi-pattern matching with bidirectional indexes ⋮ Longest Common Prefix with Mismatches ⋮ Property Suffix Array with Applications in Indexing Weighted Sequences ⋮ Pattern Discovery in Colored Strings ⋮ Reverse-Safe Text Indexing ⋮ Finding top-\(k\) longest palindromes in substrings ⋮ Two-dimensional range successor in optimal time and almost linear space ⋮ Encoding range minima and range top-2 queries ⋮ Hybrid indexes for repetitive datasets ⋮ Balancing run-length straight-line programs ⋮ Data structures for computing unique palindromes in static and non-static strings ⋮ Encoding 2D range maximum queries ⋮ Succinct permutation graphs ⋮ Space-efficient data structure for next/previous larger/smaller value queries ⋮ Unnamed Item ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Encoding nearest larger values ⋮ Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets ⋮ Unnamed Item ⋮ Succinct data structures for nearest colored node in a tree ⋮ Fast circular dictionary-matching algorithm ⋮ Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings ⋮ Minimizing the continuous diameter when augmenting a geometric tree with a shortcut ⋮ Finding maximum sum segments in sequences with uncertainty ⋮ A polynomial time algorithm to the economic lot sizing problem with constant capacity and piecewise linear concave costs ⋮ Simpler FM-index for parameterized string matching ⋮ Universal compressed text indexing ⋮ The effective entropy of next/previous larger/smaller value queries ⋮ Practical compressed suffix trees ⋮ Alphabet-independent algorithms for finding context-sensitive repeats in linear time ⋮ Searching and Indexing Circular Patterns ⋮ A Self-index on Block Trees ⋮ New variants of perfect non-crossing matchings ⋮ Finding maximal 2-dimensional palindromes ⋮ Path queries on functions ⋮ A simple linear-space data structure for constant-time range minimum query ⋮ Succinct indexes for reporting discriminating and generic words ⋮ Efficient dynamic range minimum query ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Linear-time computation of prefix table for weighted strings {\&} applications ⋮ Enumerating Range Modes ⋮ Improved exact algorithms to economic lot-sizing with piecewise linear production costs ⋮ Spaces, Trees, and Colors ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ Unnamed Item ⋮ Alignment-free sequence comparison using absent words ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Range majorities and minorities in arrays ⋮ A linear-space data structure for range-LCP queries in poly-logarithmic time ⋮ Internal dictionary matching ⋮ Compressed range minimum queries ⋮ General Document Retrieval in Compact Space ⋮ Unnamed Item ⋮ Faster algorithms for shortest path and network flow based on graph decomposition ⋮ Range minimum queries in minimal space ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Orthogonal Range Searching for Text Indexing ⋮ Improved and extended locating functionality on compressed suffix arrays ⋮ Inducing Suffix and LCP Arrays in External Memory ⋮ Lazy Lempel-Ziv Factorization Algorithms ⋮ Practical Compact Indexes for Top-kDocument Retrieval ⋮ Compressing dictionary matching index via sparsification technique ⋮ The Heaviest Induced Ancestors Problem Revisited
This page was built for publication: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
