TY - GEN

T1 - Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching

AU - Jargalsaikhan, Davaajav

AU - Hendrian, Diptarama

AU - Yoshinaka, Ryo

AU - Shinohara, Ayumi

N1 - Funding Information:
This research was partially supported by JSPS KAKENHI Grant Numbers JP15H05-706 and JP19K20208.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

PY - 2020

Y1 - 2020

N2 - Given a text and a pattern over an alphabet, the classic exact matching problem searches for all occurrences of pattern P in text T. Unlike the exact matching problem, order-preserving pattern matching considers the relative order of elements, rather than their exact values. In this paper, we propose the first parallel algorithm for the OPPM problem. Our algorithm is based on the “duel-and-sweep” algorithm. For a pattern of length m and a text of length n, our algorithm runs in time and work on the Priority CRCW PRAM.

AB - Given a text and a pattern over an alphabet, the classic exact matching problem searches for all occurrences of pattern P in text T. Unlike the exact matching problem, order-preserving pattern matching considers the relative order of elements, rather than their exact values. In this paper, we propose the first parallel algorithm for the OPPM problem. Our algorithm is based on the “duel-and-sweep” algorithm. For a pattern of length m and a text of length n, our algorithm runs in time and work on the Priority CRCW PRAM.

KW - Order-preserving pattern matching

KW - Parallel algorithm

KW - String matching

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

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

U2 - 10.1007/978-3-030-38919-2_18

DO - 10.1007/978-3-030-38919-2_18

M3 - Conference contribution

AN - SCOPUS:85079090408

SN - 9783030389185

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 211

EP - 222

BT - SOFSEM 2020

A2 - Chatzigeorgiou, Alexander

A2 - Dondi, Riccardo

A2 - Herodotou, Herodotos

A2 - Kapoutsis, Christos

A2 - Manolopoulos, Yannis

A2 - Papadopoulos, George A.

A2 - Sikora, Florian

PB - Springer

T2 - 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020

Y2 - 20 January 2020 through 24 January 2020

ER -