Parallel construction and query of index data structures for pattern matching on square matrices

DOI10.1006/jcom.1998.0496zbMath0921.68048OpenAlexW2058858161MaRDI QIDQ1288531

Raffaele Giancarlo, Roberto Grossi

Publication date: 11 May 1999

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/654057d498697519831b71ff346418160d970dda

zbMATH Keywords

fast parallel algorithms

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the construction of classes of suffix trees for square matrices: Algorithms and applications
• Parallel construction of a suffix tree with applications
• On saving space in parallel computation
• Improved deterministic parallel integer sorting
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• Two-dimensional dictionary matching
• Finding level-ancestors in trees
• Faster optimal parallel prefix sums and list ranking
• Symmetry breaking for suffix tree construction
• Suffix Arrays: A New Method for On-Line String Searches
• An Efficient Parallel Biconnectivity Algorithm
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Parallel Merge Sort
• Parallel Prefix Computation
• Finding the maximum, merging, and sorting in a parallel computation model
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms
• On the Parallel Dynamic Dictionary Matching problem: New results with applications
• Parallel Suffix–Prefix-Matching Algorithm and Applications
• A Generalization of the Suffix Tree to Square Matrices, with Applications
• An index data structure for matrices, with applications to fast two-dimensional pattern matching
• Optimal parallel suffix tree construction