Parallel construction of wavelet trees on multicore architectures

Simple item page
dc.contributor.authorFuentes-SepĂșlveda, JosĂ©
dc.contributor.authorElejalde, Erick
dc.contributor.authorFerres, Leo
dc.contributor.authorSeco, Diego
dc.date.accessioned2017-11-08T15:16:50Z
dc.date.available2017-11-08T15:16:50Z
dc.date.issued01/06/2017
dc.description.abstractThe 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 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 time and bits of extra space, where p is the number of available cores. Both algorithms are practical and report good speedup for large real datasets.
dc.description.versionVersiĂłn Publicada
dc.format.extent23 p.
dc.identifier.citationFuentes-SepĂșlveda, J., Elejalde, E., Ferres, L. et al. Parallel construction of wavelet trees on multicore architectures. Knowl Inf Syst 51, 1043–1066 (2017). https://doi.org/10.1007/s10115-016-1000-6
dc.identifier.urihttp://hdl.handle.net/11447/1728
dc.identifier.urihttps://doi.org/10.1007/s10115-016-1000-6
dc.language.isoen_US
dc.sourceKnowledge and Information Systems
dc.subjectSuccinct data structure
dc.subjectWavelet tree construction
dc.subjectMulticore
dc.subjectParallel algorithm
dc.titleParallel construction of wavelet trees on multicore architectures
dc.typeArtĂ­culo

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Parallel construction of wavelet trees on multicore architectures.pdf
Size:
1.53 MB
Format:
Adobe Portable Document Format
Description:
Texto completo restringido
Download

Collections

ArtĂ­culos IngenierĂ­a

Implementado por OpenGeek Services