Parallel construction of a suffix tree with applications |
| |
Authors: | A. Apostolico C. Iliopoulos G. M. Landau B. Schieber U. Vishkin |
| |
Affiliation: | (1) Department of Computer Sciences, Purdue University, 47907 West Lafayette, IN, USA;(2) Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, 69978 Tel Aviv, Israel;(3) Department of Computer Science, Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, 10012 New York, NY, USA |
| |
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 (n2) space. However, the space needed can be reduced toO(n1+) 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 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. |
| |
Keywords: | Parallel algorithms CRCW RAM Suffix trees On-line string matching Longest repeated substring in a string Approximate string matching Skeleton trees Processor allocation techniques |
本文献已被 SpringerLink 等数据库收录! |
|