Parallel construction of a suffix tree with applications

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

Research output: Contribution to journalArticlepeer-review

71 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 Θ(n2) space. However, the space needed can be reduced to O(n1+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 languageEnglish (US)
Pages (from-to)347-365
Number of pages19
JournalAlgorithmica
Volume3
Issue number1
DOIs
StatePublished - Mar 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • 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

Fingerprint

Dive into the research topics of 'Parallel construction of a suffix tree with applications'. Together they form a unique fingerprint.

Cite this