Optimal parallel two dimensional pattern matching

Amihood Amir; Gary Benson; Martin Farach

doi:10.1145/165231.165242

Optimal parallel two dimensional pattern matching

Amihood Amir, Gary Benson, Martin Farach

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a parallel algorithm for two dimensional matching. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(logm) on a CREW PRAM, thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(loglogro). Finding such an algorithm was a problem posed in 1985 and has been open since.

Original language	English (US)
Title of host publication	Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
Publisher	Association for Computing Machinery, Inc
Pages	79-85
Number of pages	7
ISBN (Electronic)	0897915992, 9780897915991
DOIs	https://doi.org/10.1145/165231.165242
State	Published - Aug 1 1993
Event	5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993 - Velen, Germany Duration: Jun 30 1993 → Jul 2 1993

Publication series

Name	Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993

Conference

Conference	5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993
Country/Territory	Germany
City	Velen
Period	6/30/93 → 7/2/93

Keywords

Analysis of algorithms
Multidimensional matching
Parallel algorithms
Period
String

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture

Access to Document

10.1145/165231.165242

Cite this

Amir, A., Benson, G., & Farach, M. (1993). Optimal parallel two dimensional pattern matching. In Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993 (pp. 79-85). (Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993). Association for Computing Machinery, Inc. https://doi.org/10.1145/165231.165242

Optimal parallel two dimensional pattern matching. / Amir, Amihood; Benson, Gary; Farach, Martin.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993. Association for Computing Machinery, Inc, 1993. p. 79-85 (Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Amir, A, Benson, G & Farach, M 1993, Optimal parallel two dimensional pattern matching. in Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993. Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993, Association for Computing Machinery, Inc, pp. 79-85, 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993, Velen, Germany, 6/30/93. https://doi.org/10.1145/165231.165242

@inproceedings{272a117ae67c4b06b8c09961e5d6c2ce,

title = "Optimal parallel two dimensional pattern matching",

abstract = "We present a parallel algorithm for two dimensional matching. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(logm) on a CREW PRAM, thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(loglogro). Finding such an algorithm was a problem posed in 1985 and has been open since.",

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

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

note = "Publisher Copyright: {\textcopyright} 1993 ACM.; 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993 ; Conference date: 30-06-1993 Through 02-07-1993",

year = "1993",

month = aug,

day = "1",

doi = "10.1145/165231.165242",

language = "English (US)",

series = "Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993",

publisher = "Association for Computing Machinery, Inc",

pages = "79--85",

booktitle = "Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993",

}

TY - GEN

T1 - Optimal parallel two dimensional pattern matching

AU - Amir, Amihood

AU - Benson, Gary

AU - Farach, Martin

PY - 1993/8/1

Y1 - 1993/8/1

N2 - We present a parallel algorithm for two dimensional matching. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(logm) on a CREW PRAM, thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(loglogro). Finding such an algorithm was a problem posed in 1985 and has been open since.

AB - We present a parallel algorithm for two dimensional matching. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes time O(logm) on a CREW PRAM, thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in time O(loglogro). Finding such an algorithm was a problem posed in 1985 and has been open since.

KW - Analysis of algorithms

KW - Multidimensional matching

KW - Parallel algorithms

KW - Period

KW - String

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

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

U2 - 10.1145/165231.165242

DO - 10.1145/165231.165242

M3 - Conference contribution

AN - SCOPUS:84939942016

T3 - Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993

SP - 79

EP - 85

BT - Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993

PB - Association for Computing Machinery, Inc

T2 - 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1993

Y2 - 30 June 1993 through 2 July 1993

ER -

Optimal parallel two dimensional pattern matching

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this