Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies

摘要

A compressed suffix tree usually consists of three components: a compressed suffix array, a compressedrnLCP-array, and a succinct representation of the suffix tree topology. There are parallel algorithms thatrnconstruct the suffix array and the LCP-array, but none for the third component. In this article, we presentrnparallel algorithms on shared memory architectures that construct the balanced parentheses sequencern(BPS), an explicit succinct representation of the suffix tree topology, as well as the enhanced balancedrnparentheses representation (eBPR), an implicit succinct representation of the suffix tree topology. For bothrnrepresentations, this article presents a sequential construction algorithm (a new one for the BPS), a linearrnwork and O(log n) time parallel construction algorithm, and a heuristic parallel construction algorithm thatrnworks very well in practice. The experimental results show that our methods are well suited for real-worldrnapplications.