Improved parallel construction of wavelet trees and rank/select structures

Improved parallel construction of wavelet trees and rank/select structures

Existing parallel algorithms for wavelet tree construction have a work complexity of O(nlog⁡σ). This paper presents parallel algorithms for the problem with improved work complexity. Our first algorithm is based on parallel integer sorting and has either O(nlog⁡log⁡n⌈log⁡σ/log⁡nlog⁡log⁡n⌉) work and...

Full description

Bibliographic Details
Main Author: Shun, Julian
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:English
Published: Elsevier BV 2021
Online Access:https://hdl.handle.net/1721.1/130424

Internet

https://hdl.handle.net/1721.1/130424

Similar Items