GPU Implementation of the Wavelet Tree
By: Marco Franzreb, Martin Burtscher, Stephan Rudolph
Potential Business Impact:
Makes computers find information much faster.
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.
Similar Papers
Matrix representation and GPU-optimized parallel B-spline computing
Distributed, Parallel, and Cluster Computing
Makes computer design programs much faster.
Engineering Select Support for Hybrid Bitvectors
Data Structures and Algorithms
Makes computers find data faster and use less space.
Theory Meets Practice for Bit Vectors Supporting Rank and Select
Data Structures and Algorithms
Makes computer data smaller and faster to find.