Parallel construction of a suffix tree with applications | Zendy

Alberto Apostolico | Zendy; Costa S. Iliopoulos | Zendy; Gad M. Landau | Zendy; Baruch Schieber | Zendy; Uzi Vishkin | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Parallel construction of a suffix tree with applications

Author(s) -

Alberto Apostolico,

Costa S. Iliopoulos,

Gad M. Landau,

Baruch Schieber,

Uzi Vishkin

Publication year - 1988

Publication title -

algorithmica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.647

H-Index - 78

eISSN - 1432-0541

pISSN - 0178-4617

DOI - 10.1007/bf01762122

Subject(s) - suffix tree , generalized suffix tree , suffix , compressed suffix array , theory of computation , string (physics) , computer science , tree (set theory) , combinatorics , parallel algorithm , suffix array , mathematics , data structure , discrete mathematics , algorithm , parallel computing , programming language , linguistics , philosophy , mathematical physics

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 ofn symbols inO(logn) time withn processors. The algorithm requires Θ(n 2) space. However, the space needed can be reduced toO(n 1+ɛ) for any 0< ɛ ≤1, with a corresponding slow-down proportional to 1/ɛ. Efficient parallel procedures are also given for some string problems that can be solved with suffix trees.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research