Engineering order-preserving pattern matching with SIMD parallelism

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • University of Catania
  • Istanbul Technical University

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.

Details

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

    Research areas

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

Download statistics

No data available

ID: 9202054