Optimal parallel two dimensional text searching on a CREW PRAM
type: Item
instance of: scholarly article
title: Optimal parallel two dimensional text searching on a CREW PRAM
zbMATH Open document ID: 0917.68049
author: Amihood Amir
author: G. Benson
author: Martin Farach-Colton
published in: Information and Computation
publication date: 1999-03-25T00:00:00Z
review text: In this paper, the efficient parallel algorithm for two dimensional pattern matching over a general alphabet is presented. The text processing phase is optimal in that its work is linear and its running time is optimal; i.e., it matches the lower bound \(O(\log m)\) for CREW PRAMs, where \(m\) is the length of the longest dimension of the pattern. Furthermore, it makes no assumptions about the character alphabet. On a CRCW PRAM, the algorithm runs optimally in time \(O(\log \log m),\) thus matching the lower bound for string matching on a PRAM without concurrent writes. The design of such an algorithm was posed as an open problem by \textit{U. Vishkin} [Optimal parallel pattern matching in strings, \textit{in} ``Proceeding 12th ICALP,'' 91-113 (1985)].
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68T10
zbMATH DE Number: 1220701
zbMATH Keywords: parallel algorithm for two dimensional text searching
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: two dimensional matching problem
zbMATH Keywords: period
zbMATH Keywords: string
zbMATH Keywords: pattern preprocessing
zbMATH Keywords: block compatibility
zbMATH Keywords: fast pattern matching
reviewed by: Nikolay Yakovlevich Tikhonenko
MaRDI profile type: Publication
full work available at URL: inco.1998.2705
OpenAlex ID: W1975363716
cites work: Two-Dimensional Periodicity in Rectangular Arrays
cites work: An Alphabet Independent Approach to Two-Dimensional Pattern Matching
cites work: Optimal Two-Dimensional Compressed Matching
cites work: Efficient string matching
cites work: A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
cites work: An Optimal $O(\log\log n)$ Time Parallel String Matching Algorithm
cites work: A fast string searching algorithm
cites work: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
cites work: Relations between Concurrent-Write Models of Parallel Computation
cites work: Q4230346
cites work: Q4023519
cites work: Fast Pattern Matching in Strings
cites work: Q3679094
cites work: Optimal parallel pattern matching in strings
DOI: 10.1006/INCO.1998.2705
description: scientific article; zbMATH DE number 1220701