Bertil Schmidt

Tim Dortmann, Markus Vieth, Bertil Schmidt

Approximate Membership Query (AMQ) structures are essential for high-throughput systems in databases, networking, and bioinformatics. While Bloom filters offer speed, they lack support for deletions. Existing GPU-based dynamic alternatives, such as the Two-Choice Filter (TCF) and GPU Quotient Filter (GQF), enable deletions but incur severe performance penalties. We present Cuckoo-GPU, an open-source, high-performance Cuckoo filter library for GPUs. Instead of prioritizing cache locality, Cuckoo-GPU embraces the inherently random access pattern of Cuckoo hashing to fully saturate global memory bandwidth. Our design features a lock-free architecture built on atomic compare-and-swap operations, paired with a novel breadth-first search-based eviction heuristic that minimizes thread divergence and bounds sequential memory accesses during high-load insertions. Evaluated on NVIDIA GH200 (HBM3) and RTX PRO 6000 Blackwell (GDDR7) systems, Cuckoo-GPU closes the performance gap between append-only and dynamic AMQ structures. It achieves insertion, query, and deletion throughputs up to 378x (4.1x), 6x (34.7x), and 258x (107x) higher than GQF (TCF) on the same hardware, respectively, and delivers up to a 350x speedup over the fastest available multi-threaded CPU-based Cuckoo filter implementation. Moreover, its query throughput rivals that of the append-only GPU-based Blocked Bloom filter - demonstrating that dynamic AMQ structures can be deployed on modern accelerators without sacrificing performance.

Lara Kreis, Justus Henneberg, Valentin Henkys et al.

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: severe memory overhead, high index construction time, and 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. 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 ~8x higher throughput than LCA, ~17x higher throughput than RTXRMQ, and up to ~4800x higher throughput compared to an optimized CPU-based approach.

Hinrich B Winther, Christian Hundt, Bertil Schmidt et al.

Background: Cardiac MRI derived biventricular mass and function parameters, such as end-systolic volume (ESV), end-diastolic volume (EDV), ejection fraction (EF), stroke volume (SV), and ventricular mass (VM) are clinically well established. Image segmentation can be challenging and time-consuming, due to the complex anatomy of the human heart. Objectives: This study introduces $ν$-net (/nju:n$\varepsilon$t/) -- a deep learning approach allowing for fully-automated high quality segmentation of right (RV) and left ventricular (LV) endocardium and epicardium for extraction of cardiac function parameters. Methods: A set consisting of 253 manually segmented cases has been used to train a deep neural network. Subsequently, the network has been evaluated on 4 different multicenter data sets with a total of over 1000 cases. Results: For LV EF the intraclass correlation coefficient (ICC) is 98, 95, and 80 % (95 %), and for RV EF 96, and 87 % (80 %) on the respective data sets (human expert ICCs reported in parenthesis). The LV VM ICC is 95, and 94 % (84 %), and the RV VM ICC is 83, and 83 % (54 %). This study proposes a simple adjustment procedure, allowing for the adaptation to distinct segmentation philosophies. $ν$-net exhibits state of-the-art performance in terms of dice coefficient. Conclusions: Biventricular mass and function parameters can be determined reliably in high quality by applying a deep neural network for cardiac MRI segmentation, especially in the anatomically complex right ventricle. Adaption to individual segmentation styles by applying a simple adjustment procedure is viable, allowing for the processing of novel data without time-consuming additional training.