Engineering order-preserving pattern matching with SIMD parallelism

Tamanna Chhabra*, Simone Faro, M. Oğuzhan Külekci, Jorma Tarhio

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

7 Citations (Scopus)
110 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)731–739
JournalSOFTWARE-PRACTICE AND EXPERIENCE
Volume47
Issue number5
Early online date2016
DOIs
Publication statusPublished - May 2017
MoE publication typeA1 Journal article-refereed

Keywords

  • AVX/AVX2 order-preserving pattern matching
  • SIMD
  • SSE

Fingerprint Dive into the research topics of 'Engineering order-preserving pattern matching with SIMD parallelism'. Together they form a unique fingerprint.

  • Cite this