Practical Parallel Block Tree Construction: First Results
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915698047975424 |
|---|---|
| author | Clausecker, Robert Kurpicz, Florian Palanga, Etienne |
| author_facet | Clausecker, Robert Kurpicz, Florian Palanga, Etienne |
| contents | The block tree [Belazzougui et al., J. Comput. Syst. Sci. '21] is a compressed representation of a length-$n$ text that supports access, rank, and select queries while requiring only $O(z\log\frac{n}{z})$ words of space, where $z$ is the number of Lempel-Ziv factors of the text. In other words, its space-requirements are asymptotically similar to those of the compressed text. In practice, block trees offer comparable query performance to state-of-the-art compressed rank and select indices. However, their construction is significantly slower. Additionally, the fastest construction algorithms require a significant amount of working memory. To address this issue, we propose fast and lightweight parallel algorithms for the efficient construction of block trees. Our algorithm achieves similar speed than the currently fastest construction algorithm on one core and is up to four times faster using 64 cores. It achieves all that while requiring an order of magnitude less memory. As result of independent interest, we present a data parallel algorithm for Karp-Rabin fingerprint computation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23314 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Practical Parallel Block Tree Construction: First Results Clausecker, Robert Kurpicz, Florian Palanga, Etienne Data Structures and Algorithms The block tree [Belazzougui et al., J. Comput. Syst. Sci. '21] is a compressed representation of a length-$n$ text that supports access, rank, and select queries while requiring only $O(z\log\frac{n}{z})$ words of space, where $z$ is the number of Lempel-Ziv factors of the text. In other words, its space-requirements are asymptotically similar to those of the compressed text. In practice, block trees offer comparable query performance to state-of-the-art compressed rank and select indices. However, their construction is significantly slower. Additionally, the fastest construction algorithms require a significant amount of working memory. To address this issue, we propose fast and lightweight parallel algorithms for the efficient construction of block trees. Our algorithm achieves similar speed than the currently fastest construction algorithm on one core and is up to four times faster using 64 cores. It achieves all that while requiring an order of magnitude less memory. As result of independent interest, we present a data parallel algorithm for Karp-Rabin fingerprint computation. |
| title | Practical Parallel Block Tree Construction: First Results |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.23314 |