Sorry, you need to enable JavaScript to visit this website.

Bit-Parallel (Compressed) Wavelet Tree Construction

Citation Author(s):
Patrick Dinklage, Johannes Fischer, Florian Kurpicz, Jan-Philipp Tarnowski
Submitted by:
Patrick Dinklage
Last updated:
23 February 2023 - 9:59am
Document Type:
Presentation Slides
Document Year:
Patrick Dinklage
Paper Code:

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.

1 user has voted: Nathaniel Brown