License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.2
URN: urn:nbn:de:0030-drops-87087
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8708/
Henriques, Rui ;
Francisco, Alexandre P. ;
Russo, Luís M. S. ;
Bannai, Hideo
Order-Preserving Pattern Matching Indeterminate Strings
Abstract
Given an indeterminate string pattern p and an indeterminate string text t, the problem of order-preserving pattern matching with character uncertainties (muOPPM) is to find all substrings of t that satisfy one of the possible orderings defined by p. When the text and pattern are determinate strings, we are in the presence of the well-studied exact order-preserving pattern matching (OPPM) problem with diverse applications on time series analysis. Despite its relevance, the exact OPPM problem suffers from two major drawbacks: 1) the inability to deal with indetermination in the text, thus preventing the analysis of noisy time series; and 2) the inability to deal with indetermination in the pattern, thus imposing the strict satisfaction of the orders among all pattern positions. In this paper, we provide the first polynomial algorithms to answer the muOPPM problem when: 1) indetermination is observed on the pattern or text; and 2) indetermination is observed on both the pattern and the text and given by uncertainties between pairs of characters. First, given two strings with the same length m and O(r) uncertain characters per string position, we show that the muOPPM problem can be solved in O(mr lg r) time when one string is indeterminate and r in N^+ and in O(m^2) time when both strings are indeterminate and r=2. Second, given an indeterminate text string of length n, we show that muOPPM can be efficiently solved in polynomial time and linear space.
BibTeX - Entry
@InProceedings{henriques_et_al:LIPIcs:2018:8708,
author = {Rui Henriques and Alexandre P. Francisco and Lu{\'\i}s M. S. Russo and Hideo Bannai},
title = {{Order-Preserving Pattern Matching Indeterminate Strings}},
booktitle = {Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
pages = {2:1--2:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-074-3},
ISSN = {1868-8969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8708},
URN = {urn:nbn:de:0030-drops-87087},
doi = {10.4230/LIPIcs.CPM.2018.2},
annote = {Keywords: Order-preserving pattern matching, Indeterminate string analysis, Generic pattern matching, Satisfiability}
}
|
Keywords: |
|
Order-preserving pattern matching, Indeterminate string analysis, Generic pattern matching, Satisfiability |
|
Collection: |
|
Annual Symposium on Combinatorial Pattern Matching (CPM 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
18.05.2018 |
