Simple, Fast and Lightweight Parallel Wavelet Tree Construction

DOI10.1137/1.9781611975055.2MaRDI QIDQ5232717zbMATH OpenOpenAlexFDO

Authors Johannes Fischer, Florian Kurpicz, Marvin Löbel

Publication date 12 September 2019

Published in 2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.07578

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: The wavelet tree (Grossi et al. [SODA, 2003]) and wavelet matrix (Claude et al. [Inf. Syst., 47:15--32, 2015]) are compact indices for texts over an alphabet $[0,sigma)$ that support rank, select and access queries in $O(lgsigma)$ time. We first present new practical sequential and parallel algorithms for wavelet tree construction. Their unifying characteristics is that they construct the wavelet tree bottomup}, i.e., they compute the last level first. We also show that this bottom-up construction can easily be adapted to wavelet matrices. In practice, our best sequential algorithm is up to twice as fast as the currently fastest sequential wavelet tree construction algorithm (Shun [DCC, 2015]), simultaneously saving a factor of 2 in space. This scales up to 32 cores, where we are about equally fast as the currently fastest parallel wavelet tree construction algorithm (Labeit et al. [DCC, 2016]), but still use only about 75 % of the space. An additional theoretical result shows how to adapt any wavelet tree construction algorithm to the wavelet matrix in the same (asymptotic) time, using only little extra space.

Recommendations

• Fast wavelet tree construction in practice
• Fast construction of wavelet trees
• Improved parallel construction of wavelet trees and rank/select structures
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory
• Practical Wavelet Tree Construction
• On wavelet tree construction

Cited in

(6)

• Accelerated partial decoding in wavelet trees
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Practical Wavelet Tree Construction
• Fast wavelet tree construction in practice
• Parallel external memory wavelet tree and wavelet matrix construction
• Improved parallel construction of wavelet trees and rank/select structures

This page was built for publication: Simple, Fast and Lightweight Parallel Wavelet Tree Construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232717)