Parallel construction of wavelet trees on multicore architectures / دانلود فایل

مشخصات کلی Parallel construction of wavelet trees on multicore architectures

نویسنده کتاب (Author):

Fuentes Sepúlveda, José; Elejalde, Erick; Ferres, Leo; Seco, Diego

انتشارات (Publisher):

Springer U K 2016-10-05

ویرایش و نوع فایل (Edition/Format):

 Downloadable article : English

منبع (Database):

WorldCat

عنوان ژورنال (Publication):

fuentes-sepulveda-j-elejalde-e-ferres-l-et-al-knowl-inf-syst-2016-doi10-1007s10115-016-1000-6

موضوع (Subject):

Succinct data structure       Wavelet tree construction       Multicore       View all subjects      

توضیحات خلاصه (Summary):

[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⁡σ+σlg⁡n) 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(lg⁡n) time and O(nlgσ+pσlgn/lgσ)O(nlg⁡σ+pσlg⁡n/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.  Read more…

ژانر / فرم:info:eu-repo/semantics/article

موضوع:Internet resource

نوع منبع:Internet Resource, Article

تمام نویسندگان / همکاران: Fuentes Sepúlveda, José; Elejalde, Erick; Ferres, Leo; Seco, Diego

شناسه OCLC:979265307

Language Note:English

فهرست محتوا:0219-1377 0219-3116 http://hdl.handle.net/2183/18149 10.1007/s10115-016-1000-6