Papers for

software developers for search systems

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Gpu method reduces memory use for text indexing transform

Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing

Abstract: The Burrows-Wheeler transform (BWT) is the core of many compressed full-text indexes and most read aligners. The fastest BWT constructions on GPUs need about $20$ bytes of device memory per character, which severely limits the texts that can be processed there. For example, on our GPU with 24 GB device memory, this is only about 1200 MiB. Prefix-free parsing (PFP) can be used to reduce the memory requirements of BWT construction algorithms in main memory. But, it uses hash tables and inverted lists which are not suited for GPUs. We show that PFP-based BWT construction can work with only sorting, scanning, and simple data-parallel procedures. This results in our GPU construction gpupfpbwt that on an NVIDIA RTX 3090, reduces the peak memory on an English text 11.9 bytes per character. There, it can processes 2108 MiB input files, which is 1.8 times larger than what the current state of the art libcubwt can handle. It is faster than or on par with libcubwt on eight of nine repetitive texts but 2.0 to 3.2 times slower on five of six non-repetitive ones, i.e., it provides a trade-off between required device memory and throughput.

Sat 24 OctData Structures and Algorithms
The gist
When computers search or align sequences of text, they use a technique called the Burrows-Wheeler transform that usually needs a lot of memory, especially on graphics cards. The authors found a way to build this transform using less memory on a GPU by changing the way data is organized and processed, avoiding complex structures unsuitable for GPUs. Their approach works well on repetitive texts, allowing larger files to be processed than previous methods, but it is slower on less repetitive ones. This approach offers a trade-off between using less GPU memory and running speed.
Open → 2610.33889v1