Order preserving pattern matching on trees and DAGs

Temma Nakamura; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-319-67428-5_23

Order preserving pattern matching on trees and DAGs

Temma Nakamura, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

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

5 Citations (Scopus)

Abstract

The order preserving pattern matching (OPPM) problem is, given a pattern string p and a text string t, find all substrings of t which have the same relative orders as p. In this paper, we consider two variants of the OPPM problem where a set of text strings is given as a tree or a DAG. We show that the OPPM problem for a single pattern p of length m and a text tree T of size N can be solved in O(m+N) time with O(m) working space if the characters of p are drawn from an integer alphabet of polynomial size. The time complexity becomes O(m log m + N) if the pattern p is over a general ordered alphabet. We then show that the OPPM problem for a single pattern and a text DAG is NP-complete.

Original language	English
Title of host publication	String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings
Editors	Rossano Venturini, Gabriele Fici, Marinella Sciortino
Publisher	Springer Verlag
Pages	271-277
Number of pages	7
ISBN (Print)	9783319674278
DOIs	https://doi.org/10.1007/978-3-319-67428-5_23
Publication status	Published - 2017
Event	24th International Symposium on String Processing and Information Retrieval, SPIRE 2017 - Palermo, Italy Duration: Sept 26 2017 → Sept 29 2017

Publication series

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

Other

Other	24th International Symposium on String Processing and Information Retrieval, SPIRE 2017
Country/Territory	Italy
City	Palermo
Period	9/26/17 → 9/29/17

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-67428-5_23

Cite this

Nakamura, T., Inenaga, S., Bannai, H., & Takeda, M. (2017). Order preserving pattern matching on trees and DAGs. In R. Venturini, G. Fici, & M. Sciortino (Eds.), String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings (pp. 271-277). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10508 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-67428-5_23

Order preserving pattern matching on trees and DAGs. / Nakamura, Temma; Inenaga, Shunsuke; Bannai, Hideo et al.
String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. ed. / Rossano Venturini; Gabriele Fici; Marinella Sciortino. Springer Verlag, 2017. p. 271-277 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10508 LNCS).

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

Nakamura, T, Inenaga, S, Bannai, H & Takeda, M 2017, Order preserving pattern matching on trees and DAGs. in R Venturini, G Fici & M Sciortino (eds), String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10508 LNCS, Springer Verlag, pp. 271-277, 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017, Palermo, Italy, 9/26/17. https://doi.org/10.1007/978-3-319-67428-5_23

Nakamura T, Inenaga S, Bannai H, Takeda M. Order preserving pattern matching on trees and DAGs. In Venturini R, Fici G, Sciortino M, editors, String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. Springer Verlag. 2017. p. 271-277. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-67428-5_23

Nakamura, Temma ; Inenaga, Shunsuke ; Bannai, Hideo et al. / Order preserving pattern matching on trees and DAGs. String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings. editor / Rossano Venturini ; Gabriele Fici ; Marinella Sciortino. Springer Verlag, 2017. pp. 271-277 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a0817205f28f4eb5b2692ea3845c291c,

title = "Order preserving pattern matching on trees and DAGs",

abstract = "The order preserving pattern matching (OPPM) problem is, given a pattern string p and a text string t, find all substrings of t which have the same relative orders as p. In this paper, we consider two variants of the OPPM problem where a set of text strings is given as a tree or a DAG. We show that the OPPM problem for a single pattern p of length m and a text tree T of size N can be solved in O(m+N) time with O(m) working space if the characters of p are drawn from an integer alphabet of polynomial size. The time complexity becomes O(m log m + N) if the pattern p is over a general ordered alphabet. We then show that the OPPM problem for a single pattern and a text DAG is NP-complete.",

author = "Temma Nakamura and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017 ; Conference date: 26-09-2017 Through 29-09-2017",

year = "2017",

doi = "10.1007/978-3-319-67428-5_23",

language = "English",

isbn = "9783319674278",

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

publisher = "Springer Verlag",

pages = "271--277",

editor = "Rossano Venturini and Gabriele Fici and Marinella Sciortino",

booktitle = "String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Order preserving pattern matching on trees and DAGs

AU - Nakamura, Temma

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - The order preserving pattern matching (OPPM) problem is, given a pattern string p and a text string t, find all substrings of t which have the same relative orders as p. In this paper, we consider two variants of the OPPM problem where a set of text strings is given as a tree or a DAG. We show that the OPPM problem for a single pattern p of length m and a text tree T of size N can be solved in O(m+N) time with O(m) working space if the characters of p are drawn from an integer alphabet of polynomial size. The time complexity becomes O(m log m + N) if the pattern p is over a general ordered alphabet. We then show that the OPPM problem for a single pattern and a text DAG is NP-complete.

AB - The order preserving pattern matching (OPPM) problem is, given a pattern string p and a text string t, find all substrings of t which have the same relative orders as p. In this paper, we consider two variants of the OPPM problem where a set of text strings is given as a tree or a DAG. We show that the OPPM problem for a single pattern p of length m and a text tree T of size N can be solved in O(m+N) time with O(m) working space if the characters of p are drawn from an integer alphabet of polynomial size. The time complexity becomes O(m log m + N) if the pattern p is over a general ordered alphabet. We then show that the OPPM problem for a single pattern and a text DAG is NP-complete.

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

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

U2 - 10.1007/978-3-319-67428-5_23

DO - 10.1007/978-3-319-67428-5_23

M3 - Conference contribution

AN - SCOPUS:85030168258

SN - 9783319674278

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

SP - 271

EP - 277

BT - String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings

A2 - Venturini, Rossano

A2 - Fici, Gabriele

A2 - Sciortino, Marinella

PB - Springer Verlag

T2 - 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017

Y2 - 26 September 2017 through 29 September 2017

ER -

Order preserving pattern matching on trees and DAGs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this