Parallel construction of a suffix tree: Extended abstract

Gad M. Landau; Baruch Schieber; Uzi Vishkin

doi:10.1007/3-540-18088-5_26

Parallel construction of a suffix tree: Extended abstract

Gad M. Landau, Baruch Schieber, Uzi Vishkin

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Scopus citations

Abstract

Weiner's [We-73] suffix tree is known to be a powerful tool for string manipulations. We present a parallel algorithm for constructing a suffix tree. The algorithm runs in O(log n) time and uses n processors. We also present applications for designing efficient parallel algorithms for several string problems.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 14th International Colloquium, Proceedings
Editors	Thomas Ottmann
Publisher	Springer Verlag
Pages	314-325
Number of pages	12
ISBN (Print)	9783540180883
DOIs	https://doi.org/10.1007/3-540-18088-5_26
State	Published - 1987
Externally published	Yes
Event	14th International Colloquium on Automata, Languages, and Programming, ALP 1987 - Karlsruhe, Germany Duration: Jul 13 1987 → Jul 17 1987

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	267 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Colloquium on Automata, Languages, and Programming, ALP 1987
Country/Territory	Germany
City	Karlsruhe
Period	7/13/87 → 7/17/87

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-18088-5_26

Cite this

Landau, G. M., Schieber, B., & Vishkin, U. (1987). Parallel construction of a suffix tree: Extended abstract. In T. Ottmann (Ed.), Automata, Languages and Programming - 14th International Colloquium, Proceedings (pp. 314-325). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 267 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-18088-5_26

Landau, Gad M. ; Schieber, Baruch ; Vishkin, Uzi. / Parallel construction of a suffix tree : Extended abstract. Automata, Languages and Programming - 14th International Colloquium, Proceedings. editor / Thomas Ottmann. Springer Verlag, 1987. pp. 314-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ad8d0977a7394b358a86e0dcab17e229,

title = "Parallel construction of a suffix tree: Extended abstract",

abstract = "Weiner's [We-73] suffix tree is known to be a powerful tool for string manipulations. We present a parallel algorithm for constructing a suffix tree. The algorithm runs in O(log n) time and uses n processors. We also present applications for designing efficient parallel algorithms for several string problems.",

author = "Landau, {Gad M.} and Baruch Schieber and Uzi Vishkin",

note = "Publisher Copyright: {\textcopyright} 1987, Springer-Verlag.; 14th International Colloquium on Automata, Languages, and Programming, ALP 1987 ; Conference date: 13-07-1987 Through 17-07-1987",

year = "1987",

doi = "10.1007/3-540-18088-5_26",

language = "English (US)",

isbn = "9783540180883",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "314--325",

editor = "Thomas Ottmann",

booktitle = "Automata, Languages and Programming - 14th International Colloquium, Proceedings",

address = "Germany",

}

Landau, GM, Schieber, B & Vishkin, U 1987, Parallel construction of a suffix tree: Extended abstract. in T Ottmann (ed.), Automata, Languages and Programming - 14th International Colloquium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 267 LNCS, Springer Verlag, pp. 314-325, 14th International Colloquium on Automata, Languages, and Programming, ALP 1987, Karlsruhe, Germany, 7/13/87. https://doi.org/10.1007/3-540-18088-5_26

Parallel construction of a suffix tree: Extended abstract. / Landau, Gad M.; Schieber, Baruch; Vishkin, Uzi.
Automata, Languages and Programming - 14th International Colloquium, Proceedings. ed. / Thomas Ottmann. Springer Verlag, 1987. p. 314-325 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 267 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Parallel construction of a suffix tree

T2 - 14th International Colloquium on Automata, Languages, and Programming, ALP 1987

AU - Landau, Gad M.

AU - Schieber, Baruch

AU - Vishkin, Uzi

PY - 1987

Y1 - 1987

N2 - Weiner's [We-73] suffix tree is known to be a powerful tool for string manipulations. We present a parallel algorithm for constructing a suffix tree. The algorithm runs in O(log n) time and uses n processors. We also present applications for designing efficient parallel algorithms for several string problems.

AB - Weiner's [We-73] suffix tree is known to be a powerful tool for string manipulations. We present a parallel algorithm for constructing a suffix tree. The algorithm runs in O(log n) time and uses n processors. We also present applications for designing efficient parallel algorithms for several string problems.

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

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

U2 - 10.1007/3-540-18088-5_26

DO - 10.1007/3-540-18088-5_26

M3 - Conference contribution

AN - SCOPUS:84936653165

SN - 9783540180883

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 314

EP - 325

BT - Automata, Languages and Programming - 14th International Colloquium, Proceedings

A2 - Ottmann, Thomas

PB - Springer Verlag

Y2 - 13 July 1987 through 17 July 1987

ER -

Landau GM, Schieber B, Vishkin U. Parallel construction of a suffix tree: Extended abstract. In Ottmann T, editor, Automata, Languages and Programming - 14th International Colloquium, Proceedings. Springer Verlag. 1987. p. 314-325. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-18088-5_26

Parallel construction of a suffix tree: Extended abstract

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this