A filtration method for order-preserving matching

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Chhabra, Tamanna
dc.contributor.author Tarhio, Jorma
dc.date.accessioned 2017-03-28T12:14:26Z
dc.date.available 2017-03-28T12:14:26Z
dc.date.issued 2016-02-01
dc.identifier.citation Chhabra , T & Tarhio , J 2016 , ' A filtration method for order-preserving matching ' INFORMATION PROCESSING LETTERS , vol 116 , no. 2 , pp. 71-74 . DOI: 10.1016/j.ipl.2015.10.005 en
dc.identifier.issn 0020-0190
dc.identifier.issn 1872-6119
dc.identifier.other PURE UUID: ff66a573-c2bb-4d21-8414-6eaf484d728c
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/a-filtration-method-for-orderpreserving-matching(ff66a573-c2bb-4d21-8414-6eaf484d728c).html
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=84946138393&partnerID=8YFLogxK
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/11424255/1_s2.0_S0020019015001775_main.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/25034
dc.description.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. en
dc.format.extent 4
dc.format.extent 71-74
dc.format.mimetype application/pdf
dc.language.iso en en
dc.relation.ispartofseries INFORMATION PROCESSING LETTERS en
dc.relation.ispartofseries Volume 116, issue 2 en
dc.rights openAccess en
dc.subject.other Information Systems en
dc.subject.other Computer Science Applications en
dc.subject.other Signal Processing en
dc.subject.other Theoretical Computer Science en
dc.subject.other 113 Computer and information sciences en
dc.title A filtration method for order-preserving matching en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department Department of Computer Science
dc.subject.keyword Algorithms
dc.subject.keyword Combinatorial problems
dc.subject.keyword Order-preserving matching
dc.subject.keyword String searching
dc.subject.keyword Information Systems
dc.subject.keyword Computer Science Applications
dc.subject.keyword Signal Processing
dc.subject.keyword Theoretical Computer Science
dc.subject.keyword 113 Computer and information sciences
dc.identifier.urn URN:NBN:fi:aalto-201703283273
dc.identifier.doi 10.1016/j.ipl.2015.10.005
dc.type.version publishedVersion


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account