Optimal Succinctness for Range Minimum Queries

DOI10.1007/978-3-642-12200-2_16zbMath1283.68141arXiv0812.2775OpenAlexW1565650557MaRDI QIDQ3557018

Johannes Fischer

Publication date: 27 April 2010

Published in: LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0812.2775

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items

The range 1 query (R1Q) problem ⋮ Practical space-efficient index for structural pattern matching ⋮ Lempel Ziv Computation in Small Space (LZ-CISS) ⋮ Space Efficient Data Structures for Nearest Larger Neighbor ⋮ Colored range queries and document retrieval ⋮ On compressing and indexing repetitive sequences ⋮ Space-efficient data-analysis queries on grids ⋮ On compressing permutations and adaptive sorting ⋮ Improved algorithms for the range next value problem and applications ⋮ Wavelet trees for all ⋮ On reporting the \(L_1\) metric closest pair in a query rectangle ⋮ Improved space-time tradeoffs for approximate full-text indexing with one edit error ⋮ A simple linear-space data structure for constant-time range minimum query ⋮ Efficient dynamic range minimum query ⋮ Self-indexing Based on LZ77 ⋮ LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations ⋮ LRM-trees: compressed indices, adaptive sorting, and compressed permutations ⋮ Reporting and counting maximal points in a query orthogonal rectangle ⋮ On space efficient two dimensional range minimum data structures ⋮ Linear-space data structures for range mode query in arrays ⋮ Combined data structure for previous- and next-smaller-values ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Compact and succinct data structures for multidimensional orthogonal range searching ⋮ A Space-Optimal Grammar Compression. ⋮ From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures ⋮ Array Range Queries ⋮ Unnamed Item ⋮ Inducing Suffix and LCP Arrays in External Memory ⋮ Succinct Color Searching in One Dimension ⋮ Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies ⋮ Linear-space data structures for range frequency queries on arrays and trees

This page was built for publication: Optimal Succinctness for Range Minimum Queries