Improved Parallel Construction of Wavelet Trees and Rank/Select Structures
Existing parallel algorithms for wavelet tree construction have a work complexity of $O(n\logσ)$. 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(n\log\log n\lceil\logσ/\sqrt{\log n\log\...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | مقال |
| منشور في: |
2016
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://arxiv.org/abs/1610.03524 http://arxiv.org/abs/1610.03524 |
| الوسوم: |
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|