GPU Implementation of the Wavelet Tree
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910929590943744 |
|---|---|
| author | Franzreb, Marco Burtscher, Martin Rudolph, Stephan |
| author_facet | Franzreb, Marco Burtscher, Martin Rudolph, Stephan |
| contents | I present a new GPU implementation of the wavelet tree data structure. It includes binary rank and select support structures that provide at least 10 times higher throughput of binary rank and select queries than the best publicly available CPU implementations at comparable storage overhead. My work also presents a new parallel tree construction algorithm that, when excluding the time to copy the data from the CPU to the GPU, outperforms the current state of the art. The GPU implementation, given enough parallelism, processes access, rank, and select queries at least 2x faster than the wavelet tree implementation contained in the widely used Succinct Data Structure Library (SDSL), including the time necessary to copy the queries from the CPU to the GPU and the results back to the CPU from the GPU. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_03372 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | GPU Implementation of the Wavelet Tree Franzreb, Marco Burtscher, Martin Rudolph, Stephan Data Structures and Algorithms I present a new GPU implementation of the wavelet tree data structure. It includes binary rank and select support structures that provide at least 10 times higher throughput of binary rank and select queries than the best publicly available CPU implementations at comparable storage overhead. My work also presents a new parallel tree construction algorithm that, when excluding the time to copy the data from the CPU to the GPU, outperforms the current state of the art. The GPU implementation, given enough parallelism, processes access, rank, and select queries at least 2x faster than the wavelet tree implementation contained in the widely used Succinct Data Structure Library (SDSL), including the time necessary to copy the queries from the CPU to the GPU and the results back to the CPU from the GPU. |
| title | GPU Implementation of the Wavelet Tree |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.03372 |