Paper Info
Title
Parallel Lightweight Wavelet Tree, Suffix Array and FM-Index Construction.
Abstract
We present parallel lightweight algorithms to construct wavelet trees, rank and select structures, and suffix arrays in a shared-memory setting. The work and depth of our first parallel wavelet tree algorithm match those of the best existing parallel algorithm while requiring asymptotically less memory and our second algorithm achieves the same asymptotic bounds for small alphabet sizes. Our experiments show that they are both faster and more memory-efficient than existing parallel algorithms. We also present an experimental evaluation of the parallel construction of rank and select structures, which are used in wavelet trees. Next, we design the first parallel suffix array algorithm based on induced copying. Our induced copying requires linear work and polylogarithmic depth for constant alphabets sizes. When combined with a parallel prefix doubling algorithm, it is more efficient in practice both in terms of running time and memory usage compared to existing parallel implementations. As an application, we combine our algorithms to build the FM-index in parallel.
Year
DOI
Venue
2017
10.1016/j.jda.2017.04.001
Journal of Discrete Algorithms
Keywords
DocType
Volume
Wavelet tree,Suffix array,FM index,Parallel,Induced sorting,Lightweight
Journal
43
ISSN
Citations 
PageRank 
1570-8667
5
0.43
References 
Authors
26
3
Name
Order
Citations
PageRank
Julian Labeit150.43
Julian Shun259332.57
Guy E. Blelloch32927207.30