A Simple Parallel Cartesian Tree Algorithm and its Application to Suffix Tree Construction
Feb 16, 2011
ABSTRACT: We present a simple linear work and space, and polylogarithmic 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 [1,...,n], where n is the length of the input string. More generally, given a sorted sequences of strings and the longest common prefi x 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.