Jumbled matching with SIMD

Sukhpal Ghuman, Jorma Tarhio

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

Abstract

Jumbled pattern matching addresses the problem of finding all permuted occurrences of a substring in a text. We introduce two improved algorithms for exact jumbled matching of short patterns. Our solutions apply SIMD (Single Instruction Multiple Data) computation in order to quickly filter the text. One of them utilizes the equal any operation and the other searches for the least frequent character of the pattern. Our experiments show that the best algorithm is 30% faster than previous algorithms for short English patterns.
Original languageEnglish
Title of host publicationPrague Stringology Conference 2016, August 29-31, 2016
EditorsJan Holub, Jan Zdarek
Place of PublicationPrague, Czech Republic
PublisherCzech Technical University
Pages114-124
ISBN (Print)978-80-01-05996-8
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventPrague Stringology Conference - Prague, Czech Republic
Duration: 29 Aug 201631 Aug 2016

Conference

ConferencePrague Stringology Conference
Abbreviated titlePSC
CountryCzech Republic
CityPrague
Period29/08/201631/08/2016

Fingerprint Dive into the research topics of 'Jumbled matching with SIMD'. Together they form a unique fingerprint.

Cite this