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 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.
A. Apostolico, On context-constrained squares and repetitions in a string,RAIRO Theoretical Informatics,18 (1984), 147–159.
A. Apostolico, The myriad virtues of subword trees, in A. Apostolico and Z. Galil (editors),Combinatorial Algorithms on Words, NATO ASI Series, Series F: Computer and System Sciences, Vol. 12, Springer-Verlag, Berlin, 1985, pp. 85–96.
A. Apostolico and R. Giancarlo, The Boyer-Moore-Galil string searching strategies revisited,SIAM Journal on Computing,15 (1986), 98–105.
A. Apostolico and C. Iliopoulos, Parallel log-time construction of suffix trees, CSD TR 632, Department of Computer Science, Purdue University, Sept. 1986.
A. Apostolico and F. P. Preparata, Optimal off-line detection of repetitions in a string,Theoretical Computer Science,22 (1983), 297–315.
A. Apostolico and F. P. Preparata, Structural properties of the string statistics problem,Journal of Computer and System Sciences,31 (1985), 394–411.
A. Apostolico and F. P. Preparata, Data structures and algorithms for the string statistics problem, CSD TR 541, Department of Computer Science, Purdue University, Sept. 1985.
A. Borodin and J. E. Hopcroft, Routing, merging and sorting on parallel models of computation,Journal of Computer and System Science,30 (1985), 130–145.
R. Cole and U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking,Information and Control,70 (1986), 32–53.
R. Cole and U. Vishkin, Approximate and exact parallel scheduling with applications to list, tree, and graph problems,Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986, pp. 478–491.
M. Fisher and L. Ladner, Parallel prefix computation,Journal of the Association for Computing Machinery,27 (1980), 831–838.
Z. Galil, Open problems in stringology, in A. Apostolico and Z. Galil (editors),Combinatorial Algorithms on Words, NATO ASI Series, Series F: Computer and System Sciences, Vol. 12, Springer-Veriag, Berlin, 1985, pp. 1–10.
R. M. Karp, R. E. Miller, and A. L. Rosenberg, Rapid identification of repeated patterns in strings, trees, and arrays,Proceedings of the 4th ACM Symposium on Theory of Computing, 1972, pp. 125–136.
C. P. Kruskal, Searching, merging, and sorting in parallel computation,IEEE Transactions on Computers,32 (1983), 942–946.
G. M. Landau, B. Schieber, and U. Vishkin, Parallel construction of a suffix tree, TR-53/86, Department of Computer Science, Tel Aviv University, 1986, and alsoProceedings of the 14th ICALP, Lecture Notes in Computer Science, Vol. 267, Springer-Verlag, Berlin, 1987, pp. 314–325.
G. M. Landau and U. Vishkin, Introducing efficient parallelism into approximate string matching,Proceedings of the 18th ACM Symposium on Theory of Computing, 1986, pp. 220–230.
E. M. McCreight, A space-economical suffix tree construction algorithm,Journal of the Association for Computing Machinery,23 (1976), 262–272.
B. Schieber and U. Vishkin, Parallel computation of lowest common ancestor in trees, TR-63/87, Department of Computer Science, Tel Aviv University, 1987.
Y. Shiloach and U. Vishkin, Finding the maximum, merging, and sorting in a parallel model of computation,Journal of Algorithms,2 (1981), 88–102.
L. G. Valiant, Parallelism in comparison problems,SIAM Journal on Computing,4 (1975), 348–355.
U. Vishkin, Synchronous parallel computation—a survey, TR-71, Department of Computer Science, Courant Institute, New York University, 1983.
U. Vishkin, Randomized speed-ups in parallel computation,Proceedings of the 16th ACM Symposium on Theory of Computing, 1984, pp. 230–239.
P. Weiner, Linear pattern matching algorithm,Proceedings of the 14th IEEE Symposium on Switching and Automata Theory, 1973, pp. 1–11.
Author information
Authors and Affiliations
Additional information
Communicated by Jeffrey Scott Vitter.
The results of this paper have been achieved independently and simultaneously in [AI-86] and [LSV-86]. The research of U. Vishkin was supported by NSF Grant NSF-CCR-8615337, ONR Grant N00014-85-K-0046, and Foundation for Research in Electronics, Computers, and Communication, administered by the Israeli Academy of Sciences and Humanities. The research of A. Apostolico was carried out in part while visiting at the Istituto di Analisi dei Sistemi e Informatica, Rome, with support from the Italian National Research Council. The research of G. M. Landau, B. Schieber, and U. Vishkin was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under Contract DE-AC02-76ER03077.
Rights and permissions
About this article
Cite this article
Apostolico, A., Iliopoulos, C., Landau, G.M. et al. Parallel construction of a suffix tree with applications. Algorithmica 3, 347–365 (1988). https://doi.org/10.1007/BF01762122
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01762122