Parallel construction of a suffix tree with applications

DOI10.1007/BF01762122zbMath0646.68080WikidataQ56431597 ScholiaQ56431597MaRDI QIDQ1104104

Costas S. Iliopoulos, Baruch Schieber, Gad M. Landau, Uzi Vishkin, Alberto Apostolico

Publication date: 1988

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

approximate string matchingsuffix treeCRCW parallel RAM algorithmlongest repeated substringon-line string matchingprocessor allocation techniquesskeleton trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Theory of operating systems (68N25)

Related Items (26)

An efficient parallel algorithm for the single function coarsest partition problem ⋮ On the construction of classes of suffix trees for square matrices: Algorithms and applications ⋮ On two-dimensional pattern matching by optimal parallel algorithms ⋮ Pattern matching in a digitized image ⋮ Optimal parallel randomized renaming ⋮ Sorting strings and constructing digital search trees in parallel ⋮ Fast parallel Lyndon factorization with applications ⋮ Parallel construction of minimal suffix and factor automata ⋮ Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays ⋮ Efficient parallel algorithms to test square-freeness and factorize strings ⋮ Optimal parallel algorithms for Prefix Matching ⋮ Optimal algorithms for computing the canonical form of a circular string ⋮ An efficient algorithm for the all pairs suffix-prefix problem ⋮ Optimal parallel detection of squares in strings ⋮ On-line construction of two-dimensional suffix trees ⋮ On similarity of polynomial configurations ⋮ Efficient CRCW-PRAM algorithms for universal substring searching ⋮ A quick tour on suffix arrays and compressed suffix arrays ⋮ Forty Years of Text Indexing ⋮ Optimal parallel suffix tree construction ⋮ Parallelism and dictionary based data compression ⋮ Fast parallel and serial multidimensional approximate array matching ⋮ Counter based suffix tree for DNA pattern repeats ⋮ Searching Long Repeats in Streams ⋮ Efficient text fingerprinting via Parikh mapping ⋮ Parallel construction and query of index data structures for pattern matching on square matrices

Cites Work

• Structural properties of the string statistics problem
• Routing, merging, and sorting on parallel models of computation
• Optimal off-line detection of repetitions in a string
• Searching, Merging, and Sorting in Parallel Computation
• The Boyer–Moore–Galil String Searching Strategies Revisited
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Prefix Computation
• Finding the maximum, merging, and sorting in a parallel computation model
• Parallelism in Comparison Problems
• A Space-Economical Suffix Tree Construction Algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parallel construction of a suffix tree with applications