Counting mismatches with SIMD

Fernando Fiori, Waltteri Pakalén, Jorma Tarhio

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

We consider the k mismatches version of approximate string matching for a single pattern and multiple patterns. For these problems we present new algorithms utilizing the SIMD (Single Instruction Multiple Data) instruction set extensions for patterns of up to 32 characters. We apply SIMD computation in two ways: in counting of mismatches and in calculation of fingerprints. We demonstrate the competitiveness of our solutions by practical experiments.
Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2017
EditorsJan Holub, Jan Zdarek
PublisherCzech Technical University
Pages51-61
ISBN (Print)978-80-01-06193-0
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventPrague Stringology Conference - Prague, Czech Republic
Duration: 28 Aug 201730 Aug 2017
Conference number: 21

Conference

ConferencePrague Stringology Conference
Abbreviated titlePSC
Country/TerritoryCzech Republic
CityPrague
Period28/08/201730/08/2017

Keywords

  • Approximate string matching
  • SIMD instructions
  • algorithm engineering

Fingerprint

Dive into the research topics of 'Counting mismatches with SIMD'. Together they form a unique fingerprint.

Cite this