Parallel construction of a suffix tree with applications

TY - JOUR

T1 - Parallel construction of a suffix tree with applications

AU - Apostolico, A.

AU - Iliopoulos, C.

AU - Landau, G. M.

AU - Schieber, B.

AU - Vishkin, U.

PY - 1988/11

Y1 - 1988/11

N2 - Many string manipulations can be performed efficiently on suffix trees. In this paper a CRCW parallel RAM algorithm is presented that constructs the suffix tree associated with a string of n symbols in O(log n) time with n processors. The algorithm requires Θ(n 2) space. However, the space needed can be reduced to O(n 1+e{open}) for any 0< e{open} ≤1, with a corresponding slow-down proportional to 1/e{open}. Efficient parallel procedures are also given for some string problems that can be solved with suffix trees.

AB - Many string manipulations can be performed efficiently on suffix trees. In this paper a CRCW parallel RAM algorithm is presented that constructs the suffix tree associated with a string of n symbols in O(log n) time with n processors. The algorithm requires Θ(n 2) space. However, the space needed can be reduced to O(n 1+e{open}) for any 0< e{open} ≤1, with a corresponding slow-down proportional to 1/e{open}. Efficient parallel procedures are also given for some string problems that can be solved with suffix trees.

KW - Approximate string matching

KW - CRCW RAM

KW - Longest repeated substring in a string

KW - On-line string matching

KW - Parallel algorithms

KW - Processor allocation techniques

KW - Skeleton trees

KW - Suffix trees

UR - http://www.scopus.com/inward/record.url?scp=34248344089&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34248344089&partnerID=8YFLogxK

U2 - 10.1007/BF01762122

DO - 10.1007/BF01762122

M3 - Article

SN - 0178-4617

VL - 3

SP - 347

EP - 365

JO - Algorithmica

JF - Algorithmica

IS - 1-4

ER -