We present a simple linear work and space, and poly-logarithmic time parallel algorithm for generating multiway Cartesian trees. As a special case, the algorithm can be used to generate suffix trees from suffix arrays on arbitrary alphabets in the same bounds. In conjunction with parallel suffix array algorithms, such as the skew algorithm, this gives a rather simple linear work parallel algorithm for generating suffix trees over an integer alphabet ∑ {is contained in} [1,....,n], where n is the length of the input string. More generally, given a sorted sequences of strings and the longest common prefix lengths between adjacent elements, the algorithm will generate a pat tree (compacted trie) over the strings. We also present experimental results comparing the performance of the algorithm to existing sequential implementations and a second parallel algorithm. We present comparisons for the Cartesian tree algorithm on its own and for constructing a suffix tree using our algorithm. The results show that on a variety of strings our algorithm is competitive with the sequential version on a single processor and achieves good speedup on multiple processors.
展开▼
