1994/01/01 by S. Cenk Sahinalp, Uzi Vishkin · 2 citations
Computer Science · #Algorithms and Data Compression #semigroups and automata theory #Network Packet Processing and Optimization #Citation #Computer science #Suffix #Library science #World Wide Web
paper · pdf · doi:10.1145/195058.195164
openalex publication_date 1994/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
There are several serial algorithms for suffix tree construction 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 similar 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 labels using the Deterministic Coin Tossing (DCT) technique, and thereby reduce the number of labeled substrings to linear. We give several algorithms for suffix tree construction. One of them runs in 0(log2 n) parallel time and O(n) work for input strings whose characters are drawn from a constant size alphabet.