Engineering order-preserving pattern matching with SIMD parallelism
Loading...
Access rights
openAccess
proof
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)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
SOFTWARE-PRACTICE AND EXPERIENCE, Volume 47, issue 5, pp. 731–739
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
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