Symmetry Breaking In Suffix Tree Construction

Sahinalp SC, Vishkin U.
23 May 1994
Proc. of STOC 1994, 300-309
Presented at STOC’94 (Twenty-Sixth Annual ACM Symposium on Theory of Computing), Montreal, QC Canada, May 23-25

Abstract

There are several serial algorithms for suffix tree construc- tion which run in linear time, but the number of operations in the only parallel algorithm available, due to Apostolic, Iliopoulos, Landau, Schieber and VLshkin, is proportional to n log n. The algorithm is based on labeling substringsj sim- ilar to a classical serial algorithm, with the same operations bound, by Karp, Miller and Rosenberg. We show how to break symmetries that occur in the process of assigning la- bels using the Deterministic Coin Tossing (DCT) technique, and thereby reduce the number of labeled substrings to lin- ear. We give several algorithms for suffix tree construction. One of them runs in O(log^2 n) parallel time and O(n) work for input strings whose characters are drawn from a constant size alphabet.