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

Davaajav Jargalsaikhan; Diptarama Hendrian; Ryo Yoshinaka; Ayumi Shinohara

doi:10.1007/978-3-030-38919-2_18

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

Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

INF - System Information Sciences

Tohoku University

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

1 Citation (Scopus)

Abstract

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.

Original language	English
Title of host publication	SOFSEM 2020
Subtitle of host publication	Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings
Editors	Alexander Chatzigeorgiou, Riccardo Dondi, Herodotos Herodotou, Christos Kapoutsis, Yannis Manolopoulos, George A. Papadopoulos, Florian Sikora
Publisher	Springer
Pages	211-222
Number of pages	12
ISBN (Print)	9783030389185
DOIs	https://doi.org/10.1007/978-3-030-38919-2_18
Publication status	Published - 2020
Event	46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020 - Limassol, Cyprus Duration: 2020 Jan 20 → 2020 Jan 24

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12011 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020
Country/Territory	Cyprus
City	Limassol
Period	20/1/20 → 20/1/24

Keywords

Order-preserving pattern matching
Parallel algorithm
String matching

Access to Document

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

Cite this

Jargalsaikhan, D., Hendrian, D., Yoshinaka, R., & Shinohara, A. (2020). Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching. In A. Chatzigeorgiou, R. Dondi, H. Herodotou, C. Kapoutsis, Y. Manolopoulos, G. A. Papadopoulos, & F. Sikora (Eds.), SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings (pp. 211-222). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12011 LNCS). Springer. https://doi.org/10.1007/978-3-030-38919-2_18

Jargalsaikhan, Davaajav ; Hendrian, Diptarama ; Yoshinaka, Ryo et al. / Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching. SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings. editor / Alexander Chatzigeorgiou ; Riccardo Dondi ; Herodotos Herodotou ; Christos Kapoutsis ; Yannis Manolopoulos ; George A. Papadopoulos ; Florian Sikora. Springer, 2020. pp. 211-222 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{898d111f31ed4e9ca53ae74abb478ad1,

title = "Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching",

abstract = "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.",

keywords = "Order-preserving pattern matching, Parallel algorithm, String matching",

author = "Davaajav Jargalsaikhan and Diptarama Hendrian and Ryo Yoshinaka and Ayumi Shinohara",

note = "Funding Information: This research was partially supported by JSPS KAKENHI Grant Numbers JP15H05-706 and JP19K20208. Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020 ; Conference date: 20-01-2020 Through 24-01-2020",

year = "2020",

doi = "10.1007/978-3-030-38919-2_18",

language = "English",

isbn = "9783030389185",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "211--222",

editor = "Alexander Chatzigeorgiou and Riccardo Dondi and Herodotos Herodotou and Christos Kapoutsis and Yannis Manolopoulos and Papadopoulos, {George A.} and Florian Sikora",

booktitle = "SOFSEM 2020",

address = "Germany",

}

Jargalsaikhan, D, Hendrian, D , Yoshinaka, R & Shinohara, A 2020, Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching. in A Chatzigeorgiou, R Dondi, H Herodotou, C Kapoutsis, Y Manolopoulos, GA Papadopoulos & F Sikora (eds), SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12011 LNCS, Springer, pp. 211-222, 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020, Limassol, Cyprus, 20/1/20. https://doi.org/10.1007/978-3-030-38919-2_18

Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching. / Jargalsaikhan, Davaajav; Hendrian, Diptarama ; Yoshinaka, Ryo et al.
SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings. ed. / Alexander Chatzigeorgiou; Riccardo Dondi; Herodotos Herodotou; Christos Kapoutsis; Yannis Manolopoulos; George A. Papadopoulos; Florian Sikora. Springer, 2020. p. 211-222 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12011 LNCS).

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

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

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 -

Jargalsaikhan D, Hendrian D , Yoshinaka R , Shinohara A. Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching. In Chatzigeorgiou A, Dondi R, Herodotou H, Kapoutsis C, Manolopoulos Y, Papadopoulos GA, Sikora F, editors, SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings. Springer. 2020. p. 211-222. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-38919-2_18

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this