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 matching; suffix tree; CRCW parallel RAM algorithm; longest repeated substring; on-line string matching; processor allocation techniques; skeleton trees

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

68N25: Theory of operating systems

Related Items

Fast parallel Lyndon factorization with applications, On the construction of classes of suffix trees for square matrices: Algorithms and applications, Optimal parallel algorithms for Prefix Matching, Forty Years of Text Indexing, Searching Long Repeats in Streams, On-line construction of two-dimensional suffix trees, Optimal parallel suffix tree construction, Parallelism and dictionary based data compression, Optimal parallel randomized renaming, A quick tour on suffix arrays and compressed suffix arrays, On similarity of polynomial configurations, 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 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, Efficient CRCW-PRAM algorithms for universal substring searching, Parallel construction and query of index data structures for pattern matching on square matrices, An efficient parallel algorithm for the single function coarsest partition problem, On two-dimensional pattern matching by optimal parallel algorithms, Pattern matching in a digitized image, Sorting strings and constructing digital search trees in parallel, Efficient text fingerprinting via Parikh mapping, Fast parallel and serial multidimensional approximate array matching, Counter based suffix tree for DNA pattern repeats

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