Engineering order‐preserving pattern matching with SIMD parallelism. (24th August 2016)

• Record Type: Journal Article
• Authors: Chhabra, Tamanna; Faro, Simone; Külekci, M. Oğuzhan; Tarhio, Jorma
• Is Part Of: Software, practice & experience. Volume 47:Number 5(2017)
• Page Start: 731
• Page End: 739
• Publication Date: 2016-08-24
• Subjects: SIMD -- SSE -- AVX/AVX2 order‐preserving pattern matching; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2433
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: 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. ©2016 The Authors. Software: Practice and Experience Published by John Wiley & Sons Ltd.