A filtration method for order-preserving matching
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
2016-02-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
4
Series
Information Processing Letters, Volume 116, issue 2, pp. 71-74
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.Description
Keywords
Algorithms, Combinatorial problems, Order-preserving matching, String searching
Other note
Citation
Chhabra, T & Tarhio, J 2016, ' A filtration method for order-preserving matching ', Information Processing Letters, vol. 116, no. 2, pp. 71-74 . https://doi.org/10.1016/j.ipl.2015.10.005