The order-preserving pattern matching problem in practice

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

DISCRETE APPLIED MATHEMATICS, cilt.274, ss.11-25, 2020 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 274
  • Basım Tarihi: 2020
  • Doi Numarası: 10.1016/j.dam.2018.10.023
  • Dergi Adı: DISCRETE APPLIED MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, zbMATH
  • Sayfa Sayıları: ss.11-25
  • İstanbul Teknik Üniversitesi Adresli: Evet

Özet

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.