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.
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.