Encodings for Range Minimum Queries over Bounded Alphabets
For researchers in data structures and database management, this work provides the first systematic analysis of RMQ encodings under bounded alphabets, but the findings are largely incremental as they confirm that space bounds remain close to the general case.
The paper studies the encoding complexity of range minimum queries (RMQs) on arrays over bounded alphabets, presenting near-optimal space encodings for 1D arrays and matching upper/lower bounds for 2D arrays with various query types. The results show that bounded alphabets do not significantly reduce space requirements compared to general alphabets.
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.