GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs

Lara Kreis, Justus Henneberg, Valentin Henkys, Felix Schuhknecht, Bertil Schmidt · 2026

Read GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs by Lara Kreis, Justus Henneberg, Valentin Henkys, Felix Schuhknecht, Bertil Schmidt (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-01811.txt.

Introduction

Kreis and colleagues present GPU-RMQ for range minimum queries on GPUs, used in string and database work. Recent ray-tracing approaches express queries as rays fired into triangles for range minima, but suffer memory overhead, slow building, or low throughput. GPU-RMQ builds a hierarchy of summaries in parallel, then processes parts in a parallel scan. Its hybrid design uses ray tracing cores and CUDA cores at different levels. Tests show higher throughput than leading GPU methods, on large arrays, with a smaller footprint and faster index construction.

Catalog record

CREATORLara Kreis, Justus Henneberg, Valentin Henkys, Felix Schuhknecht, Bertil Schmidt
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57907
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.01811

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

GPU-RMQ: Accelerating Range Minimum Queries on Modern GPUs Lara Kreis, Justus Henneberg, Valentin Henkys, Felix Schuhknecht, Bertil Schmidt Abstract . Range minimum queries are frequently used in string processing and database applications including biological sequence analysis, document retrieval, and web search. Hence, various data structures have been proposed for improving their efficiency on both CPUs and GPUs. Recent work has also shown that hardware-accelerated ray tracing on modern NVIDIA RTX graphic cards can be exploited to answer range minimum queries by expressing queries as rays, which are fired into a scene of triangles representing minima of ranges at different granularities. While these approaches are promising, they suffer from at least one of three issues: (a) severe memory overhead, (b) high index construction time, and (c) low query throughput. This renders these methods practically unusable on larger arrays: For example, the state-of-art GPU-based approaches LCA and RTXRMQ exceed the memory capacity of an NVIDIA RTX 4090 GPU for input arrays of size ≥ 2 29 \geq 2^{29} . To tackle these problems, in this work, we present a new approach called GPU-RMQ which is based on a hierarchical approach. GPU-RMQ first constructs a hierarchy of range minimum summaries on top of the original array in a highly parallel fashion. For query answering, only the relevant portions of the hierarchy are then processed in an optimized massively-parallel scan operation. Additionally, GPU-RMQ is hybrid in design, enabling the use of both ray tracing cores and CUDA cores across different levels of the hierarchy to handle queries. Our experimental evaluation shows that GPU-RMQ outperforms the state-of-the-art approaches in terms of query throughput especially for larger arrays while offering a significantly lower memory footprint and up to two orders-of-magnitude faster index construction. In particular, it achieves up to ∼ 8 × \sim 8\times higher throughput than LCA , ∼ 17 × \sim 17\times higher throughput than RTXRMQ , and up to ∼ 4800 × \sim 4800\times higher throughput compared to an optimized CPU-based approach. Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/lakreis/GPU-RMQ . 1. Introduction Given an array X of n numbers, range minimum queries (RMQs) address the problem of finding the minimum value within arbitrary contiguous sub-arrays of X . They are fundamental operations and can be used for finding lowest common ancestors in trees, computing longest common extensions of suffixes, or answering maximum-sum segment queries. They are featured in a wide range of application areas including biological sequence analysis, and document retrieval. Consider, for example, the state-of-the-art long read aligner Minimap2 ( 20 ) , one of its key components, the chaining module, relies on solving RMQs and accounts for up to 35% of the tool’s total computational runtime ( 18 ) , or state-of-the-art methods for distributed suffix array construction and querying ( 10 ) . Motivated by the importance of RMQs across such diverse range of applications, their acceleration has been explored using a variety of architectures such as CPUs ( 8 ; 9 ; 6 ; 5 ; 19 ; 7 ; 27 ; 1 ) , GPUs ( 30 ; 26 ; 23 ) , and even QPUs ( 32 ) . (a) Memory footprint. (b) Construction time. (c) RMQ Throughput. Figure 1 . GPU-RMQ addresses important limitations of the prior GPU-based approaches RTXRMQ and LCA , resulting in (a) lower memory footprint, (b) significantly faster index construction times, and (c) higher throughput per RMQ (results shown for the mixed datasets (see Section 5.1 ) on an RTX 4090 GPU). For static RMQs (i.e. batched range minima are computed without updating X ), a data structure is typically built for the input array in a preprocessing step, which is then used to answer batches of RMQs. Prior GPU-based approaches rely on different types of tree data structures. Soman et al. ( 30 ) were the first to implement RMQs on GPUs by means of a Cartesian tree data structure, while Polak et al. ( 26 ) proposed LCA – a method to compute Euler tours on trees that can be used for both lowest common ancestor queries and RMQs. Meneses et al. ( 23 ) recently proposed RTXRMQ – a new method to leverage RT (ray tracing) cores to solve RMQs. Their key idea is to represent all values of the input array as a geometric scene. By launching multiple rays into this scene, RMQs can be solved in parallel by taking advantage of hardware-accelerated bounding volume hierarchy (BVH) traversal capabilities on GPUs. Unfortunately, all these approaches suffer from significant memory consumption to store the corresponding data structures in GPU memory. For example, the geometric scene constructed by RTXRMQ requires at least one triangle per array element, which limits its applicability for large input arrays due to insufficient memory resources. In addition, traversing trees on GPUs can be inefficient due to irregular memory access schemes. Figure 1 , which shows (a) memory footprint, (b) index construction time, and (c) RMQ throughput of the two state-of-the-art GPU approaches LCA and RTXRMQ on a NVIDIA RTX 4090 for various input array sizes, presents these problems: For an input array consisting of n=2^{29} elements, the memory usage of both LCA and RTXRMQ already exceeds the capacity of the utilized RTX 4090 GPU (24 GB). Further, both LCA and RTXRMQ suffer from a high construction time, which increases heavily with an increase in input size. Also, for larger input arrays that exceed the available cache, the time per RMQ heavily increases. In this work, we address these limitations by proposing an efficient hierarchical data structure and a corresponding processing scheme called GPU-RMQ . On a high-level, GPU-RMQ creates a hierarchy of range minimum summaries on top of the original array. To answer a batch of RMQs, GPU-RMQ then scans and post-filters the relevant parts of the hierarchy via highly optimized hardware-conscious scan operations using cooperative thread groups. As we can see in Figure 1 , this leads to a high RMQ throughput while consuming only a moderate amount of auxiliary memory and offering a low construction time for the data structure — enabling GPU-based processing of significantly larger arrays. Additionally, we designed GPU-RMQ as a hybrid approach in which the upper level of the hierarchy can be processed by RT cores while lower levels are handled by CUDA cores, thereby combining different hardware capabilities of modern GPUs. 1.1. Contributions and Structure of the Paper In summary, we make the following contributions in this work: (1) We propose GPU-RMQ , a highly efficient GPU-based acceleration structure for answering RMQs. On a high-level, GPU-RMQ builds a hierarchy of range minimum summaries of varying granularity. For query answering, GPU-RMQ identifies and scans the relevant parts of this hierarchy in a highly parallel fashion to compute the actual minimum. (2) GPU-RMQ integrates a set of carefully designed optimizations that aim at exploiting the characteristics of the highly-parallel hardware. This includes vector loading and coalesced loading to speed up scanning, as well as multi-loading and warp-local queuing for assigning queries to hardware threads. As these optimization techniques are configurable, we experimentally determine their impact and configuration of choice. (3) We designed GPU-RMQ from ground up as a hybrid acceleration structure, which

Read the complete text