ABOUT BOOK

The wavelet tree has become a very useful data structure to efficiently represent and query large volumes of data in many different domains, from bioinformatics to geographic information systems. One problem with wavelet trees is their construction time. In this paper, we introduce two algorithms that reduce the time complexity of a wavelet tree's construction by taking advantage of nowadays ubiquitous multicore machines. Our first algorithm constructs all the levels of the wavelet in parallel in O(n)O(n)O(n) time and O(nlg⁡σ+σlg⁡n)O(n\lg\sigma + \sigma\lg n)O(nlgσ+σlgn) bits of working space, where nnn is the size of the input sequence and σ\sigmaσ is the size of the alphabet. Our second algorithm constructs the wavelet tree in a domain-decomposition fashion, using our first algorithm in each segment, reaching O(lg⁡n)O(\lg n)O(lgn) time and O(nlg⁡σ+pσlg⁡n/lg⁡σ)O(n\lg\sigma + p\sigma\lg n/\lg\sigma)O(nlgσ+pσlgn/lgσ) bits of extra space, where ppp is the number of available cores. Both algorithms are practical and report good speedup for large real datasets.Comment: This research has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie Actions H2020-MSCA-RISE-2015 BIRDS GA No. 69094