Engineering order-preserving pattern matching with SIMD parallelism

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Tutkijat

Organisaatiot

  • University of Catania
  • Istanbul Technical University

Kuvaus

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.

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut731–739
JulkaisuSOFTWARE-PRACTICE AND EXPERIENCE
Vuosikerta47
Numero5
Varhainen verkossa julkaisun päivämäärä2016
TilaJulkaistu - toukokuuta 2017
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Lataa tilasto

Ei tietoja saatavilla

ID: 9202054