Engineering order-preserving pattern matching with SIMD parallelism

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2017-05
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
SOFTWARE-PRACTICE AND EXPERIENCE
Abstract
The 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.
Description
Keywords
AVX/AVX2 order-preserving pattern matching, SIMD, SSE
Other note
Citation
Chhabra , 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.2433