Parallel construction of a suffix tree with applications

A. Apostolico; C. Iliopoulos; G. M. Landau; B. Schieber; U. Vishkin

doi:10.1007/BF01762122

Parallel construction of a suffix tree with applications

A. Apostolico, C. Iliopoulos, G. M. Landau, B. Schieber, U. Vishkin

Research output: Contribution to journal › Article › peer-review

125 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	347-365
Number of pages	19
Journal	Algorithmica
Volume	3
Issue number	1-4
DOIs	https://doi.org/10.1007/BF01762122
State	Published - Nov 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
Computer Science Applications
Applied Mathematics

Keywords

Approximate string matching
CRCW RAM
Longest repeated substring in a string
On-line string matching
Parallel algorithms
Processor allocation techniques
Skeleton trees
Suffix trees

Access to Document

10.1007/BF01762122

Cite this

@article{05cb6266dfd142e686882159a70beafc,

title = "Parallel construction of a suffix tree with applications",

abstract = "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.",

keywords = "Approximate string matching, CRCW RAM, Longest repeated substring in a string, On-line string matching, Parallel algorithms, Processor allocation techniques, Skeleton trees, Suffix trees",

author = "A. Apostolico and C. Iliopoulos and Landau, {G. M.} and B. Schieber and U. Vishkin",

year = "1988",

month = nov,

doi = "10.1007/BF01762122",

language = "English (US)",

volume = "3",

pages = "347--365",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1-4",

}

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

AN - SCOPUS:34248344089

SN - 0178-4617

VL - 3

SP - 347

EP - 365

JO - Algorithmica

JF - Algorithmica

IS - 1-4

ER -

Parallel construction of a suffix tree with applications

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this