Parallel construction of wavelet trees on multicore architectures
Use este enlace para citar
http://hdl.handle.net/2183/18149Coleccións
- GI-LBD - Artigos [51]
- OpenAIRE [357]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Parallel construction of wavelet trees on multicore architecturesData
2016-10-05Cita bibliográfica
Fuentes-Sepúlveda, J., Elejalde, E., Ferres, L. et al. Knowl Inf Syst (2016). doi:10.1007/s10115-016-1000-6
Resumo
[Abstract] 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 with O(n) time and O(nlgσ+σlgn)O(nlgσ+σlgn) bits of working space, where n is the size of the input sequence and σσ 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(lgn)O(lgn) time and O(nlgσ+pσlgn/lgσ)O(nlgσ+pσlgn/lgσ) bits of extra space, where p is the number of available cores. Both algorithms are practical and report good speedup for large real datasets.
Palabras chave
Succinct data structure
Wavelet tree construction
Multicore
Parallel algorithm
Wavelet tree construction
Multicore
Parallel algorithm
Descrición
The final publication is available at Springer via http://dx.doi.org/10.1007/s10115-016-1000-6
Versión do editor
ISSN
0219-1377
0219-3116
0219-3116