Jumbled matching with SIMD

Sukhpal Ghuman; Jorma Tarhio

Jumbled matching with SIMD

Tietotekniikan laitos

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	Prague Stringology Conference 2016, August 29-31, 2016
Toimittajat	Jan Holub, Jan Zdarek
Julkaisupaikka	Prague, Czech Republic
Kustantaja	Czech Technical University in Prague
Sivut	114-124
ISBN (painettu)	978-80-01-05996-8
Tila	Julkaistu - 2016
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	Prague Stringology Conference - Prague, Tshekki Kesto: 29 elok. 2016 → 31 elok. 2016

Conference

Conference	Prague Stringology Conference
Lyhennettä	PSC
Maa/Alue	Tshekki
Kaupunki	Prague
Ajanjakso	29/08/2016 → 31/08/2016

Pääsy asiakirjaan

http://www.stringology.org/event/2016/p10.html

OpenUrl-saatavuus

Koko teksti

Siteeraa tätä

@inproceedings{93320d28b59d422199c6497c428eeae8,

title = "Jumbled matching with SIMD",

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. ",

author = "Sukhpal Ghuman and Jorma Tarhio",

year = "2016",

language = "English",

isbn = "978-80-01-05996-8",

pages = "114--124",

editor = "Jan Holub and Jan Zdarek",

booktitle = "Prague Stringology Conference 2016, August 29-31, 2016",

publisher = "Czech Technical University in Prague",

address = "Czech Republic",

note = "Prague Stringology Conference, PSC ; Conference date: 29-08-2016 Through 31-08-2016",

}

TY - GEN

T1 - Jumbled matching with SIMD

AU - Ghuman, Sukhpal

AU - Tarhio, Jorma

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 978-80-01-05996-8

SP - 114

EP - 124

BT - Prague Stringology Conference 2016, August 29-31, 2016

A2 - Holub, Jan

A2 - Zdarek, Jan

PB - Czech Technical University in Prague

CY - Prague, Czech Republic

T2 - Prague Stringology Conference

Y2 - 29 August 2016 through 31 August 2016

ER -

Jumbled matching with SIMD

Abstrakti

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Sormenjälki

Siteeraa tätä