The order-preserving pattern matching problem in practice

Cantone D., Faro S., Külekci M. O.

DISCRETE APPLIED MATHEMATICS, vol.274, pp.11-25, 2020 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 274
  • Publication Date: 2020
  • Doi Number: 10.1016/j.dam.2018.10.023
  • Journal Name: DISCRETE APPLIED MATHEMATICS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, zbMATH
  • Page Numbers: pp.11-25
  • Istanbul Technical University Affiliated: Yes

Abstract

Given a pattern x of length m and a text y of length n, both over a totally ordered alphabet, the order-preserving pattern matching (OPPM) problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM problem, which might be viewed as an approximate variant of the well-known exact pattern matching problem, has gained attention in recent years. This interesting problem finds applications in such diverse fields as time series analysis (as share prices on stock markets or weather data analysis) and musical melody matching, just to mention a few.