A filtration method for order-preserving matching

Tamanna Chhabra, Jorma Tarhio*

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

13 Sitaatiot (Scopus)
100 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Sivut71-74
Sivumäärä4
JulkaisuInformation Processing Letters
Vuosikerta116
Numero2
DOI - pysyväislinkit
TilaJulkaistu - 1 helmikuuta 2016
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Sormenjälki Sukella tutkimusaiheisiin 'A filtration method for order-preserving matching'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Siteeraa tätä