Parallel construction of a suffix tree with applications
From MaRDI portal
Publication:1104104
DOI10.1007/BF01762122zbMath0646.68080WikidataQ56431597 ScholiaQ56431597MaRDI QIDQ1104104
Costas S. Iliopoulos, Baruch Schieber, Gad M. Landau, Alberto Apostolico, Uzi Vishkin
Publication date: 1988
Published in: Algorithmica (Search for Journal in Brave)
approximate string matching; suffix tree; CRCW parallel RAM algorithm; longest repeated substring; on-line string matching; processor allocation techniques; skeleton trees
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, 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
