A filtration method for order-preserving matching

Research output: Contribution to journalArticleScientificpeer-review

Standard

A filtration method for order-preserving matching. / Chhabra, Tamanna; Tarhio, Jorma.

In: Information Processing Letters, Vol. 116, No. 2, 01.02.2016, p. 71-74.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

APA

Vancouver

Author

Bibtex - Download

@article{ff66a573c2bb4d2184146eaf484d728c,
title = "A filtration method for order-preserving matching",
abstract = "The problem of order-preserving matching has gained attention lately. The text and the pattern consist of numbers. The task is to find all the substrings in the text which have the same length and relative order as the pattern. The problem has applications in analysis of time series. We present a new sublinear solution based on filtration. Any algorithm for exact string matching can be used as a filtering method. If the filtration algorithm is sublinear, the total method is sublinear on average. We show by practical experiments that the new solution is more efficient than earlier algorithms.",
keywords = "Algorithms, Combinatorial problems, Order-preserving matching, String searching",
author = "Tamanna Chhabra and Jorma Tarhio",
year = "2016",
month = "2",
day = "1",
doi = "10.1016/j.ipl.2015.10.005",
language = "English",
volume = "116",
pages = "71--74",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "2",

}

RIS - Download

TY - JOUR

T1 - A filtration method for order-preserving matching

AU - Chhabra, Tamanna

AU - Tarhio, Jorma

PY - 2016/2/1

Y1 - 2016/2/1

N2 - The problem of order-preserving matching has gained attention lately. The text and the pattern consist of numbers. The task is to find all the substrings in the text which have the same length and relative order as the pattern. The problem has applications in analysis of time series. We present a new sublinear solution based on filtration. Any algorithm for exact string matching can be used as a filtering method. If the filtration algorithm is sublinear, the total method is sublinear on average. We show by practical experiments that the new solution is more efficient than earlier algorithms.

AB - The problem of order-preserving matching has gained attention lately. The text and the pattern consist of numbers. The task is to find all the substrings in the text which have the same length and relative order as the pattern. The problem has applications in analysis of time series. We present a new sublinear solution based on filtration. Any algorithm for exact string matching can be used as a filtering method. If the filtration algorithm is sublinear, the total method is sublinear on average. We show by practical experiments that the new solution is more efficient than earlier algorithms.

KW - Algorithms

KW - Combinatorial problems

KW - Order-preserving matching

KW - String searching

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

U2 - 10.1016/j.ipl.2015.10.005

DO - 10.1016/j.ipl.2015.10.005

M3 - Article

VL - 116

SP - 71

EP - 74

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 2

ER -

ID: 1500385