pith. sign in

arxiv: 2604.13350 · v1 · submitted 2026-04-14 · 💻 cs.DS

Encodings for Range Minimum Queries over Bounded Alphabets

Seungbum Jo , Srinivasa Rao Satti This is my paper

Pith reviewed 2026-05-10 13:40 UTC · model grok-4.3

classification 💻 cs.DS
keywords range minimum queriesbounded alphabetsencoding spaceone-dimensional arraystwo-dimensional arrayslower boundsupper bounds
0
0 comments X

The pith

Bounded alphabets require near-optimal space for one-dimensional range minimum query encodings and tight bounds in two dimensions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper investigates the space needed to encode arrays so that range minimum queries can still be answered when every entry belongs to a small fixed set of values. In one dimension it constructs an encoding whose size is close to the information-theoretic minimum and that answers queries in constant time once the alphabet size is constant. In two dimensions it separates queries into one-sided, two-sided, three-sided, and four-sided rectangles, supplies matching lower and upper bounds on encoding space for each type, and shows that efficient query times remain possible in most of those settings. The central message is that restricting the alphabet does not let us compress the structure much below what is already known for arrays with arbitrary values. Readers care because many practical inputs, such as DNA strings or pixel grids, have small alphabets yet previously had to use the same general-purpose structures.

Core claim

For the 1D case, we present a near-optimal space encoding. For constant-sized alphabets, this also supports the queries in constant time. For the 2D case, we systematically analyze the 1-sided, 2-sided, 3-sided and 4-sided queries and derive lower bounds for encoding space, and also matching upper bounds that support efficient queries in most cases. Our results demonstrate that, even with the bounded alphabet restriction, the space requirements remain close to those for the general alphabet case.

What carries the argument

The near-optimal 1D encoding together with the sidedness classification that yields matching lower and upper space bounds for each type of 2D rectangular query.

If this is right

  • One-dimensional RMQ on constant alphabets can be answered in constant time with space close to the minimum possible.
  • Two-dimensional RMQ encodings have asymptotically tight space bounds once the number of fixed sides of the query rectangle is fixed.
  • Efficient query times remain achievable for most two-dimensional sided variants without increasing the asymptotic space cost.
  • The combinatorial arrangement of minima, rather than the numerical range of entries, is what primarily determines the encoding space.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same sidedness analysis could be applied to range-maximum or range-mode queries on bounded alphabets.
  • Practical implementations on genomic or image data could measure whether the constant-time claims survive real-machine constants.
  • If the lower bounds hold, further space savings would require a weaker query model or additional assumptions on the input distribution.

Load-bearing premise

The alphabet size is fixed and known in advance, and the computational model permits the stated constant-time bounds without hidden factors.

What would settle it

A family of one-dimensional constant-alphabet arrays whose minimum range encoding requires asymptotically more bits than the paper's claimed near-optimal size, or a two-dimensional instance whose space lower bound is not met by any structure that answers the corresponding sided queries.

Figures

Figures reproduced from arXiv: 2604.13350 by Seungbum Jo, Srinivasa Rao Satti.

Figure 1
Figure 1. Figure 1: (a) An m × n array over an alphabet of size 5, where the green positions represent the set P, partitioned into staircases S0, . . . , S4. The red and gray lines represent the lattice path L0 and L1, respectively. (b) Two distinct lattice paths in the region Rσ−2 and their corresponding staircases (denoted by circular points). For each Sℓ, we define a lattice path Lℓ from (m + 1, 0) to (0, n + 1) that satis… view at source ↗
Figure 2
Figure 2. Figure 2: (a) A single block of size √ σ × 2 √ σ of an m × n array in the set A used in the proof of Theorem 13, (b) to answer RMQ in the rectangular range (represented by the dotted line): (i) the candidate answer in the gray range can be found using RMQ on individual blocks, (ii) in the red range using RMQ on Ar, (iii) in the green range using RMQ on Ac, and (iv) in the white range using RMQ on Arc. Theorem 13. Fo… view at source ↗
read the original abstract

Range minimum queries (RMQs) are fundamental operations with widespread applications in database management, text indexing and computational biology. While many space-efficient data structures have been designed for RMQs on arrays with arbitrary elements, there has not been any results developed for the case when the alphabet size is small, which is the case in many practical scenarios where RMQ structures are used. In this paper, we investigate the encoding complexity of RMQs on arrays over bounded alphabet. We consider both one-dimensional (1D) and two-dimensional (2D) arrays. For the 1D case, we present a near-optimal space encoding. For constant-sized alphabets, this also supports the queries in constant time. For the 2D case, we systematically analyze the 1-sided, 2-sided, 3-sided and 4-sided queries and derive lower bounds for encoding space, and also matching upper bounds that support efficient queries in most cases. Our results demonstrate that, even with the bounded alphabet restriction, the space requirements remain close to those for the general alphabet case.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript studies the encoding complexity of range minimum queries (RMQs) on 1D and 2D arrays whose elements come from a bounded alphabet of size σ. For the 1D case it claims a near-optimal space encoding that supports constant-time queries whenever σ is constant. For the 2D case it derives information-theoretic lower bounds on the space needed to encode 1-sided, 2-sided, 3-sided and 4-sided RMQs and supplies matching upper-bound constructions that achieve efficient query times in most of the variants. The central message is that the bounded-alphabet restriction yields only modest space savings relative to the general-alphabet setting.

Significance. If the claimed constructions and matching bounds are correct, the work would be a useful addition to the RMQ literature. Bounded alphabets arise in many practical applications (text indexing, computational biology, database columns), yet prior encoding results have focused on arbitrary alphabets. A complete 2D analysis with both lower and upper bounds would clarify the fundamental space-query trade-offs for the four query types and could guide the design of practical succinct structures.

major comments (1)
  1. The abstract (and the reader's summary of the full text) asserts the existence of near-optimal 1D encodings and matching 2D lower/upper bounds, yet supplies no explicit theorems, constructions, or proofs. Without these, the central claims cannot be verified and the soundness assessment remains low.

Simulated Author's Rebuttal

1 responses · 0 unresolved

Thank you for reviewing our manuscript on encodings for range minimum queries over bounded alphabets. We appreciate the referee's recognition of the practical relevance of this work for applications such as text indexing, computational biology, and database management. We address the major comment below.

read point-by-point responses

  1. Referee: The abstract (and the reader's summary of the full text) asserts the existence of near-optimal 1D encodings and matching 2D lower/upper bounds, yet supplies no explicit theorems, constructions, or proofs. Without these, the central claims cannot be verified and the soundness assessment remains low.

    Authors: The abstract is a high-level summary of the results, which is standard practice. The full manuscript supplies explicit theorems, constructions, and proofs: the 1D near-optimal encoding (with constant-time queries for constant σ) is detailed with its space bound and construction, while the 2D analysis provides information-theoretic lower bounds for 1-sided, 2-sided, 3-sided, and 4-sided RMQs along with matching upper-bound constructions and query times. These appear in the main sections following the introduction. The full text therefore supports verification of the central claims that bounded alphabets yield only modest space savings relative to the general case. revision: no

Circularity Check

0 steps flagged

No significant circularity; derivations rely on independent combinatorial arguments

full rationale

The paper's central results consist of information-theoretic lower bounds on encoding space for RMQ over bounded alphabets together with explicit constructions providing matching or near-matching upper bounds. These steps are derived from standard combinatorial counting on possible arrays and query answers rather than any self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The bounded-alphabet restriction is stated upfront and used to tighten the space bounds relative to the general case, but no equation or claim reduces to its own inputs by construction. The 1D near-optimal encoding and the four 2D query variants are supported by separate lower/upper-bound arguments that remain self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Paper rests on standard data-structure assumptions; no free parameters or invented entities are visible from the abstract.

axioms (2)
  • domain assumption Word-RAM model with word size logarithmic in input size
    Required to claim constant-time queries for constant alphabets.
  • domain assumption Alphabet size sigma is constant or small and known a priori
    Central premise enabling the space savings and time bounds.

pith-pipeline@v0.9.0 · 5482 in / 1256 out tokens · 46563 ms · 2026-05-10T13:40:50.172466+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    The lca problem revisited

    Michael A Bender and Martin Farach-Colton. The lca problem revisited. InLatin American Sym- posium on Theoretical Informatics, pages 88–94. Springer, 2000

    work page 2000

  2. [2]

    The encoding complexity of two dimensional range minimum data structures

    Gerth Stølting Brodal, Andrej Brodnik, and Pooya Davoodi. The encoding complexity of two dimensional range minimum data structures. InESA, volume 8125 ofLecture Notes in Computer Science, pages 229–240. Springer, 2013

    work page 2013

  3. [3]

    Two dimensional range minimum queries and Fibonacci lattices.Theor

    Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, and Srinivasa Rao Satti. Two dimensional range minimum queries and Fibonacci lattices.Theor. Comput. Sci., 638:33–43, 2016

    work page 2016

  4. [4]

    On space efficient two dimensional range minimum data structures.Algorithmica, 63(4):815–830, 2012

    Gerth Stølting Brodal, Pooya Davoodi, and Srinivasa Rao Satti. On space efficient two dimensional range minimum data structures.Algorithmica, 63(4):815–830, 2012

    work page 2012

  5. [5]

    Succinct representations of binary trees for range minimum queries

    Pooya Davoodi, Rajeev Raman, and Srinivasa Rao Satti. Succinct representations of binary trees for range minimum queries. InComputing and Combinatorics - 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012. Proceedings, volume 7434 ofLecture Notes in Computer Science, pages 396–407. Springer, 2012. 14

    work page 2012

  6. [6]

    Demaine, Gad M

    Erik D. Demaine, Gad M. Landau, and Oren Weimann. On Cartesian trees and range minimum queries. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas, editors,Automata, Languages and Programming, pages 341–353, Berlin, Heidel- berg, 2009. Springer Berlin Heidelberg

    work page 2009

  7. [7]

    Changing base without losing space

    Yevgeniy Dodis, Mihai Patrascu, and Mikkel Thorup. Changing base without losing space. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Mas- sachusetts, USA, 5-8 June 2010, pages 593–602, 2010

    work page 2010

  8. [8]

    An alphabet-friendly FM- index

    Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro. An alphabet-friendly FM- index. InSPIRE, volume 3246 ofLecture Notes in Computer Science, pages 150–160. Springer, 2004

    work page 2004

  9. [9]

    PhD thesis, Ludwig-Maximilians- Universität München, 2007

    Johannes Fischer.Data structures for efficient string algorithms. PhD thesis, Ludwig-Maximilians- Universität München, 2007

    work page 2007

  10. [10]

    Space-efficient preprocessing schemes for range minimum queries on static arrays.SIAM J

    Johannes Fischer and Volker Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays.SIAM J. Comput., 40(2):465–492, 2011

    work page 2011

  11. [11]

    Fully functional suffix trees and optimal text searching in BWT-runs bounded space.J

    Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully functional suffix trees and optimal text searching in BWT-runs bounded space.J. ACM, 67(1):2:1–2:54, 2020

    work page 2020

  12. [12]

    Compressed range minimum queries.Theor

    Pawel Gawrychowski, Seungbum Jo, Shay Mozes, and Oren Weimann. Compressed range minimum queries.Theor. Comput. Sci., 812:39–48, 2020

    work page 2020

  13. [13]

    Asymptotic enu- meration of compacted binary trees of bounded right height.J

    Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, and Michael Wallner. Asymptotic enu- meration of compacted binary trees of bounded right height.J. Comb. Theory A, 172:105177, 2020

    work page 2020

  14. [14]

    Golin, John Iacono, Danny Krizanc, Rajeev Raman, Srinivasa Rao Satti, and Sunil M

    Mordecai J. Golin, John Iacono, Danny Krizanc, Rajeev Raman, Srinivasa Rao Satti, and Sunil M. Shende. Encoding 2D range maximum queries.Theor. Comput. Sci., 609:316–327, 2016

    work page 2016

  15. [15]

    High-orderentropy-compressedtextindexes

    RobertoGrossi, AnkurGupta, andJeffreyScottVitter. High-orderentropy-compressedtextindexes. InSODA, pages 841–850. ACM/SIAM, 2003

    work page 2003

  16. [16]

    Fast algorithms for finding nearest common ancestors.SIAM J

    Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors.SIAM J. Comput., 13(2):338–355, 1984.doi:10.1137/0213024

    work page doi:10.1137/0213024 1984

  17. [17]

    Nicholson, and Rajeev Raman

    Michael Hoffmann, John Iacono, Patrick K. Nicholson, and Rajeev Raman. Encoding nearest larger values.Theor. Comput. Sci., 710:97–115, 2018

    work page 2018

  18. [18]

    Encodings for range minimum queries over bounded al- phabets

    Seungbum Jo and Srinivasa Rao Satti. Encodings for range minimum queries over bounded al- phabets. In Paola Bonizzoni and Veli Mäkinen, editors,36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025, June 17-19, 2025, Milan, Italy, volume 331 ofLIPIcs, pages 25:1– 25:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025

    work page 2025

  19. [19]

    Full-fledged real-time indexing for constant size alphabets

    Gregory Kucherov and Yakov Nekrich. Full-fledged real-time indexing for constant size alphabets. Algorithmica, 79(2):387–400, 2017

    work page 2017

  20. [20]

    Ian Munro, Gonzalo Navarro, and Yakov Nekrich

    J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich. Text indexing and searching in sublinear time. InCPM, volume 161 ofLIPIcs, pages 24:1–24:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. 15

    work page 2020

  21. [21]

    Ian Munro, Patrick K

    J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner, and Sebastian Wild. Hypersuccinct trees-newuniversaltreesourcecodesforoptimalcompressedtreedatastructuresandrangeminima. InESA, volume 204 ofLIPIcs, pages 70:1–70:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021

    work page 2021

  22. [22]

    Wavelet trees for all.J

    Gonzalo Navarro. Wavelet trees for all.J. Discrete Algorithms, 25:2–20, 2014

    work page 2014

  23. [23]

    Succinct indexable dictionaries with applications to encodingk-ary trees, prefix sums and multisets.ACM Trans

    Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries with applications to encodingk-ary trees, prefix sums and multisets.ACM Trans. Algorithms, 3(4):43, 2007

    work page 2007

  24. [24]

    Note on the number of minimal lattice paths restricted by two parallel lines.Discret

    Masako Sato. Note on the number of minimal lattice paths restricted by two parallel lines.Discret. Math., 44(1):117–121, 1983

    work page 1983

  25. [25]

    On finding lowest common ancestors: Simplification and paral- lelization.SIAM J

    Baruch Schieber and Uzi Vishkin. On finding lowest common ancestors: Simplification and paral- lelization.SIAM J. Comput., 17(6):1253–1262, 1988.doi:10.1137/0217079

    work page doi:10.1137/0217079 1988

  26. [26]

    A unifying look at data structures.Commun

    Jean Vuillemin. A unifying look at data structures.Commun. ACM, 23(4):229–239, 1980

    work page 1980

  27. [27]

    Hao Yuan and Mikhail J. Atallah. Data structures for range minimum queries in multidimensional arrays. InSODA, pages 150–160. SIAM, 2010. 16

    work page 2010