Documents
Presentation Slides
Presentation Slides
Bit-Parallel (Compressed) Wavelet Tree Construction
- Citation Author(s):
- Submitted by:
- Patrick Dinklage
- Last updated:
- 23 February 2023 - 9:59am
- Document Type:
- Presentation Slides
- Document Year:
- 2023
- Event:
- Presenters:
- Patrick Dinklage
- Paper Code:
- 193
- Categories:
- Keywords:
- Log in to post comments
The wavelet tree is a data structure that indexes a text over an integer alphabet for efficient rank and select queries. Using the Huffman encoding, it can be stored in zero-order entropy-compressed space. We present a highly engineered open source implementation of an efficient sequential construction algorithm that makes use of bit parallelism via vector instructions. On hardware featuring ultrawide registers of up to 512 bits, it outperforms the currently fastest known practical sequential construction algorithms by a factor of up to 2.5.
slides.pdf
slides.pdf (92)