Cover Image

Encodings for Range Minimum Queries over Bounded Alphabets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jo, Seungbum, Satti, Srinivasa Rao
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Simple Representation of Tree Covering Utilizing Balanced Parentheses and Efficient Implementation of Average-Case Optimal RMQs
by: Hamada, Kou, et al.
Published: (2024)

Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries
by: Jo, Seungbum, et al.
Published: (2022)

Dynamic Range Minimum Queries on the Ultra-Wide Word RAM
by: Bille, Philip, et al.
Published: (2024)

Tokenisation over Bounded Alphabets is Hard
by: Kastreva, Violeta, et al.
Published: (2025)

Succinct Data Structures for Baxter Permutation and Related Families
by: Chakraborty, Sankardeep, et al.
Published: (2024)

Quantum Data Structure for Range Minimum Query
by: Wang, Qisheng, et al.
Published: (2026)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
by: Balakrishnan, Girish, et al.
Published: (2023)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Sorted Range Reporting and Range Minima Queries
by: Akram, Waseem, et al.
Published: (2021)

Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
by: Bruno, Roberto, et al.
Published: (2024)

Minimizing the Minimizers via Alphabet Reordering
by: Verbeek, Hilde, et al.
Published: (2024)

Improving Pinwheel Density Bounds for Small Minimums
by: Mishra, Ahan, et al.
Published: (2025)

Edit and Alphabet-Ordering Sensitivity of Lex-parse
by: Nakashima, Yuto, et al.
Published: (2024)

Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
by: Carmeli, Nofar, et al.
Published: (2025)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

Engineering Rank/Select Data Structures for Large-Alphabet Strings
by: Arroyuelo, Diego, et al.
Published: (2023)

Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
by: Con, Roni, et al.
Published: (2024)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Towards Efficient Data Structures for Approximate Search with Range Queries
by: Kian, Ladan, et al.
Published: (2026)

Range (Rényi) Entropy Queries and Partitioning
by: Esmailpour, Aryan, et al.
Published: (2023)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs
by: Kreis, Lara, et al.
Published: (2026)

Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations
by: Brown, Nathaniel K., et al.
Published: (2026)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
by: Azarmehr, Amir, et al.
Published: (2025)

Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees
by: Hu, Ivan, et al.
Published: (2022)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
by: Upirvitskiy, Aleksey, et al.
Published: (2026)

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
by: Adar, Tomer, et al.
Published: (2024)

Grafite: Taming Adversarial Queries with Optimal Range Filters
by: Costa, Marco, et al.
Published: (2023)

Old and New Results on Alphabetic Codes
by: Bruno, Roberto, et al.
Published: (2025)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
by: Zhao, Zhuowei, et al.
Published: (2025)

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
by: Cohen, Edith, et al.
Published: (2024)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
by: Kempa, Dominik, et al.
Published: (2025)

Query-decision Regression between Shortest Path and Minimum Steiner Tree
by: Tong, Guangmo, et al.
Published: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
by: Banik, Aritra, et al.
Published: (2024)

Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions
by: Lange, Jane, et al.
Published: (2023)

Data Structures for Range Sorted Consecutive Occurrence Queries
by: Akram, Waseem, et al.
Published: (2024)

Faster Pseudo-Deterministic Minimum Cut
by: Kenneth-Mordoch, Yotam
Published: (2026)

Minimum Temporal Spanners in Happy Graphs
by: Casteigts, Arnaud, et al.
Published: (2026)