Pragmatics of parallel suffix tree construction

Other Scholarly Content

Analytics

Citeable URL: https://ir.library.oregonstate.edu/concern/defaults/v692tf66d

Attribute Name	Values
Creator	Miller, Bryan
Abstract	Suffix trees are a well known data structure for facilitating a variety of queries on strings. Construction of the trees requires a considerable number of choices concerning the implementation. Several of those choices are examined in this paper. Performance studies are presented that reveal the consequences of these choices. The main focus of this paper is the implementation choices that influence suffix tree construction on parallel computers. Four algorithms are examined. Two are sequential and two are parallel. Results show that a sequential Algorithm developed by Edward McCreight generally has better performance than Alberto Apostolico's parallel algorithm on real machines. A streamlined version of Apostolico's algorithm helps parallel performance somewhat; but not enough to dethrone McCreight's design. The sequential naive algorithm studied gives a good simple reference point when understanding the other algorithms.
Resource Type	Research Paper
Date Issued	1992-12
Academic Affiliation	Computer Science
Rights Statement	In Copyright
Publisher	Oregon State University. Department of Computer Science
Peer Reviewed	No
Language	English [eng]

Thumbnail	Title	Date Uploaded	Visibility	Actions
	Miller_Bryan_1992_12.pdf	2023-03-29	Public	Download