Engineering order-preserving pattern matching with SIMD parallelism

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorChhabra, Tamanna
dc.contributor.authorFaro, Simone
dc.contributor.authorKülekci, M. Oğuzhan
dc.contributor.authorTarhio, Jorma
dc.contributor.departmentDepartment of Computer Science
dc.contributor.departmentUniversity of Catania
dc.contributor.departmentIstanbul Technical University
dc.date.accessioned2017-04-20T10:17:09Z
dc.date.available2017-04-20T10:17:09Z
dc.date.issued2017-05
dc.description.abstractThe order-preserving pattern matching problem has gained attention in recent years. It consists in finding all substrings in the text, which have the same length and relative order as the input pattern. Typically, the text and the pattern consist of numbers. Since recent times, there has been a tendency to utilize the ability of the word RAM model to increase the efficiency of string matching algorithms. This model works on computer words, reading and processing blocks of characters at once, so that usual arithmetic and logic operations on words can be performed in one unit of time. In this paper, we present a fast order-preserving pattern matching algorithm, which uses specialized word-size packed string matching instructions, grounded on the single instruction multiple data instruction set architecture. We show with experimental results that the new proposed algorithm is more efficient than the previous solutions.en
dc.description.versionPeer revieweden
dc.format.mimetypeapplication/pdf
dc.identifier.citationChhabra , T , Faro , S , Külekci , M O & Tarhio , J 2017 , ' Engineering order-preserving pattern matching with SIMD parallelism ' , SOFTWARE-PRACTICE AND EXPERIENCE , vol. 47 , no. 5 , pp. 731–739 . https://doi.org/10.1002/spe.2433en
dc.identifier.doi10.1002/spe.2433
dc.identifier.issn0038-0644
dc.identifier.otherPURE UUID: 1d7c138c-848c-4d31-b192-6022d6597a70
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/1d7c138c-848c-4d31-b192-6022d6597a70
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=84992459009&partnerID=8YFLogxK
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/11426110/Chhabra_et_al_2016_Software_Practice_and_Experience_1.pdf
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/25219
dc.identifier.urnURN:NBN:fi:aalto-201704203649
dc.language.isoenen
dc.relation.ispartofseriesSOFTWARE-PRACTICE AND EXPERIENCEen
dc.rightsopenAccessen
dc.subject.keywordAVX/AVX2 order-preserving pattern matching
dc.subject.keywordSIMD
dc.subject.keywordSSE
dc.titleEngineering order-preserving pattern matching with SIMD parallelismen
dc.typeA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäfi
dc.type.versionproof
Files