2011. A simple parallel cartesian tree algorithm and its application to suffix tree construction

We present a simple linear work and space, and polylogarithmic time parallel algorithm for generating mul-tiway Cartesian trees. We show that bottom-up traversals of the multiway Cartesian tree on the interleaved suffix array and longest common prefix array of a string can be used to answer certain string queries. By adding downward pointers in the tree (e.g. using a hash table), we can also 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, O(n) time (0 < < 1), algorithm for generating suffix trees over an integer alphabet ⊆ {1,...,n}, where n is the length of the input string. It also gives a linear work parallel algorithm requiring O(log2 n) time with high probability for constant-sized alphabets. More generally, given a sorted sequence of strings and the longest common prefix lengths between adjacent elements, the algorithm will generate a patricia tree (compacted trie) over the strings. Of independent interest, we describe a work-efficient parallel algorithm for solving the all nearest smaller values problem using Cartesian trees, which is much simpler than the work-efficient parallel algorithm described in previous work. We also present experimental results comparing the performance of the algorithm to existing sequen-tial implementations and a second parallel algorithm that we implement. We present comparisons for th