Optimal logarithmic time randomized suffix tree construction

Martin Farach; S. Muthukrishnant

doi:https://doi.org/10.1007/3-540-61440-0_158

Optimal logarithmic time randomized suffix tree construction

Martin Farach, S. Muthukrishnant

School of Arts and Sciences, Computer Science

Rutgers, The State University

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

24 Scopus citations

Abstract

The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matching, has many elegant applications. In this paper, we present a novel, simple sequential algorithm for the construction of suffix trees. We are also able to parallelize our algorithm so that we settle the main open problem in the construction of suffix trees: we give a Las Vegas CRCW PRAM algorithm that constructs the suffix tree of a binary string of length n in O(log n) time and O(n) work with high probability. In contrast, the previously known work-optimal algorithms, while deterministic, take Ω(log² n) time. We also give a work-optimal randomized comparison-based algorithm to convert any string over an unbounded alphabet to an equivalent string over a binary alphabet. As a result, we obtain the first work-optimal algorithm for suffix tree construction under the unbounded alphabet assumption.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings
Editors	Friedhelm Meyer auf der Heide, Burkhard Monien
Publisher	Springer Verlag
Pages	550-561
Number of pages	12
ISBN (Print)	3540614400, 9783540614401
DOIs	https://doi.org/10.1007/3-540-61440-0_158
State	Published - 1996
Event	23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996 - Paderborn, Germany Duration: Jul 8 1996 → Jul 12 1996

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1099

Other

Other	23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996
Country/Territory	Germany
City	Paderborn
Period	7/8/96 → 7/12/96

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

https://doi.org/10.1007/3-540-61440-0_158

Cite this

Farach, M., & Muthukrishnant, S. (1996). Optimal logarithmic time randomized suffix tree construction. In F. Meyer auf der Heide, & B. Monien (Eds.), Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings (pp. 550-561). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1099). Springer Verlag. https://doi.org/10.1007/3-540-61440-0_158

Farach, Martin ; Muthukrishnant, S. / Optimal logarithmic time randomized suffix tree construction. Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings. editor / Friedhelm Meyer auf der Heide ; Burkhard Monien. Springer Verlag, 1996. pp. 550-561 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{38509a6c4ed44bdeab8940809178c59f,

title = "Optimal logarithmic time randomized suffix tree construction",

abstract = "The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matching, has many elegant applications. In this paper, we present a novel, simple sequential algorithm for the construction of suffix trees. We are also able to parallelize our algorithm so that we settle the main open problem in the construction of suffix trees: we give a Las Vegas CRCW PRAM algorithm that constructs the suffix tree of a binary string of length n in O(log n) time and O(n) work with high probability. In contrast, the previously known work-optimal algorithms, while deterministic, take Ω(log2 n) time. We also give a work-optimal randomized comparison-based algorithm to convert any string over an unbounded alphabet to an equivalent string over a binary alphabet. As a result, we obtain the first work-optimal algorithm for suffix tree construction under the unbounded alphabet assumption.",

author = "Martin Farach and S. Muthukrishnant",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1996.; 23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996 ; Conference date: 08-07-1996 Through 12-07-1996",

year = "1996",

doi = "https://doi.org/10.1007/3-540-61440-0_158",

language = "English (US)",

isbn = "3540614400",

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

publisher = "Springer Verlag",

pages = "550--561",

editor = "{Meyer auf der Heide}, Friedhelm and Burkhard Monien",

booktitle = "Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings",

address = "Germany",

}

Farach, M & Muthukrishnant, S 1996, Optimal logarithmic time randomized suffix tree construction. in F Meyer auf der Heide & B Monien (eds), Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1099, Springer Verlag, pp. 550-561, 23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996, Paderborn, Germany, 7/8/96. https://doi.org/10.1007/3-540-61440-0_158

Optimal logarithmic time randomized suffix tree construction. / Farach, Martin; Muthukrishnant, S.
Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings. ed. / Friedhelm Meyer auf der Heide; Burkhard Monien. Springer Verlag, 1996. p. 550-561 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1099).

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

TY - GEN

T1 - Optimal logarithmic time randomized suffix tree construction

AU - Farach, Martin

AU - Muthukrishnant, S.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1996.

PY - 1996

Y1 - 1996

N2 - The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matching, has many elegant applications. In this paper, we present a novel, simple sequential algorithm for the construction of suffix trees. We are also able to parallelize our algorithm so that we settle the main open problem in the construction of suffix trees: we give a Las Vegas CRCW PRAM algorithm that constructs the suffix tree of a binary string of length n in O(log n) time and O(n) work with high probability. In contrast, the previously known work-optimal algorithms, while deterministic, take Ω(log2 n) time. We also give a work-optimal randomized comparison-based algorithm to convert any string over an unbounded alphabet to an equivalent string over a binary alphabet. As a result, we obtain the first work-optimal algorithm for suffix tree construction under the unbounded alphabet assumption.

AB - The suffix tree of a string, the fundamental data structure in the area of combinatorial pattern matching, has many elegant applications. In this paper, we present a novel, simple sequential algorithm for the construction of suffix trees. We are also able to parallelize our algorithm so that we settle the main open problem in the construction of suffix trees: we give a Las Vegas CRCW PRAM algorithm that constructs the suffix tree of a binary string of length n in O(log n) time and O(n) work with high probability. In contrast, the previously known work-optimal algorithms, while deterministic, take Ω(log2 n) time. We also give a work-optimal randomized comparison-based algorithm to convert any string over an unbounded alphabet to an equivalent string over a binary alphabet. As a result, we obtain the first work-optimal algorithm for suffix tree construction under the unbounded alphabet assumption.

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

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

U2 - https://doi.org/10.1007/3-540-61440-0_158

DO - https://doi.org/10.1007/3-540-61440-0_158

M3 - Conference contribution

SN - 3540614400

SN - 9783540614401

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

SP - 550

EP - 561

BT - Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings

A2 - Meyer auf der Heide, Friedhelm

A2 - Monien, Burkhard

PB - Springer Verlag

T2 - 23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996

Y2 - 8 July 1996 through 12 July 1996

ER -

Farach M, Muthukrishnant S. Optimal logarithmic time randomized suffix tree construction. In Meyer auf der Heide F, Monien B, editors, Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings. Springer Verlag. 1996. p. 550-561. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: https://doi.org/10.1007/3-540-61440-0_158

Optimal logarithmic time randomized suffix tree construction

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this