Optimal Parallel Two Dimensional Text Searching on a CREW PRAM

Amihood Amir; Gary Benson; Martin Farach-Colton

doi:10.1006/inco.1998.2705

Optimal Parallel Two Dimensional Text Searching on a CREW PRAM

Amihood Amir, Gary Benson, Martin Farach-Colton

Research output: Contribution to journal › Article › peer-review

Abstract

We present a parallel algorithm for two dimensional text searching over a general alphabet. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(log m) on a CREW PRAM (where m is the length of the longest dimension of the pattern), thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(log log m).

Original language	English (US)
Pages (from-to)	1-17
Number of pages	17
Journal	Information and Computation
Volume	144
Issue number	1
DOIs	https://doi.org/10.1006/inco.1998.2705
State	Published - Jul 10 1998

Keywords

Analysis of algorithms
Multidimensional matching
Parallel algorithms
Period
String

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Computer Science Applications
Computational Theory and Mathematics

Access to Document

10.1006/inco.1998.2705

Cite this

@article{cedd0f451280456fbba36777bd5c6391,

title = "Optimal Parallel Two Dimensional Text Searching on a CREW PRAM",

abstract = "We present a parallel algorithm for two dimensional text searching over a general alphabet. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(log m) on a CREW PRAM (where m is the length of the longest dimension of the pattern), thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(log log m).",

keywords = "Analysis of algorithms, Multidimensional matching, Parallel algorithms, Period, String",

author = "Amihood Amir and Gary Benson and Martin Farach-Colton",

year = "1998",

month = jul,

day = "10",

doi = "10.1006/inco.1998.2705",

language = "English (US)",

volume = "144",

pages = "1--17",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Optimal Parallel Two Dimensional Text Searching on a CREW PRAM

AU - Amir, Amihood

AU - Benson, Gary

AU - Farach-Colton, Martin

PY - 1998/7/10

Y1 - 1998/7/10

N2 - We present a parallel algorithm for two dimensional text searching over a general alphabet. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(log m) on a CREW PRAM (where m is the length of the longest dimension of the pattern), thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(log log m).

AB - We present a parallel algorithm for two dimensional text searching over a general alphabet. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(log m) on a CREW PRAM (where m is the length of the longest dimension of the pattern), thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(log log m).

KW - Analysis of algorithms

KW - Multidimensional matching

KW - Parallel algorithms

KW - Period

KW - String

UR - http://www.scopus.com/inward/record.url?scp=0347611276&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347611276&partnerID=8YFLogxK

U2 - 10.1006/inco.1998.2705

DO - 10.1006/inco.1998.2705

M3 - Article

AN - SCOPUS:0347611276

SN - 0890-5401

VL - 144

SP - 1

EP - 17

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -

Optimal Parallel Two Dimensional Text Searching on a CREW PRAM

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this