A filtration method for order-preserving matching

Tamanna Chhabra, Jorma Tarhio*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

13 Citations (Scopus)
97 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)71-74
Number of pages4
JournalInformation Processing Letters
Volume116
Issue number2
DOIs
Publication statusPublished - 1 Feb 2016
MoE publication typeA1 Journal article-refereed

Keywords

  • Algorithms
  • Combinatorial problems
  • Order-preserving matching
  • String searching

Fingerprint Dive into the research topics of 'A filtration method for order-preserving matching'. Together they form a unique fingerprint.

  • Cite this