Given a pattern x of length m and a text y of length n, both over an ordered alphabet, the order-preserving pattern matching problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM, 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 a lot of fields as from time series analysis, like share prices on stock markets or weather data analysis, to musical melody matching. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods by reducing the number of false positives up to 99 %. From our experimental results it turns out that our proposed solutions are up to 2 times faster than the previous solutions.

Efficient Algorithms for the Order Preserving Pattern Matching Problem

FARO, SIMONE;
2016-01-01

Abstract

Given a pattern x of length m and a text y of length n, both over an ordered alphabet, the order-preserving pattern matching problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM, 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 a lot of fields as from time series analysis, like share prices on stock markets or weather data analysis, to musical melody matching. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods by reducing the number of false positives up to 99 %. From our experimental results it turns out that our proposed solutions are up to 2 times faster than the previous solutions.
2016
978-3-319-41167-5
File in questo prodotto:
File Dimensione Formato  
2016 - Efficient Algorithms for the Order Preserving Pattern Matching Problem.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Dominio pubblico
Dimensione 302.08 kB
Formato Adobe PDF
302.08 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/95711
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 6
social impact