TY - GEN
T1 - Optimal parallel two dimensional pattern matching
AU - Amir, Amihood
AU - Benson, Gary
AU - Farach, Martin
N1 - Publisher Copyright:
© 1993 ACM.
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
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 -