Engineering the counting filter for string matching algorithms

Uproszczony widok
dc.contributor.authorSusik, Robert
dc.contributor.authorGrabowski, Szymon
dc.date.accessioned2021-05-05T07:01:07Z
dc.date.available2021-05-05T07:01:07Z
dc.date.issued2016
dc.description.abstractWe consider a new approach to the popular counting filter technique for approximate pattern matching. Our solution is based on q-grams combined with alphabet reduction by bin packing and using Streaming SIMD Extensions (SSE). We present a few variants that use the mentioned techniques and discuss pros and cons of them considering two approximate pattern matching problems. The first one is the well- known matching with k-differences and the second one is a biological problem of DNA sequence mutation called matching with inversions and translocations. The experimental results show the effectiveness of our ideas that speed up the counting filter and reduce the number of verifications by orders of magnitude.en_EN
dc.identifier.citationSusik R., Grabowski Sz., Engineering the counting filter for string matching algorithms. W: Algorithms, Networking and Sensing for Data Processing, Mobile Computing and Applications, Romanowski A. (red.), Sankowski D. (red), Sikora J. (red.), Lodz University of Technology Press, Łódź 2016, s. 125-140, ISBN 978-83-7283-738-7.
dc.identifier.isbn978-83-7283-738-7
dc.identifier.urihttp://hdl.handle.net/11652/3401
dc.language.isoenen_EN
dc.publisherWydawnictwo Politechniki Łódzkiejpl_PL
dc.publisherLodz University of Technology Pressen_EN
dc.relation.ispartofRomanowski A. (red.), Sankowski D. (red), Sikora J. (red.), Algorithms, Networking and Sensing for Data Processing, Mobile Computing and Applications, Lodz University of Technology Press, Łódź 2016, ISBN 978-83-7283-738-7.
dc.relation.ispartofseriesMonografie Politechniki Łódzkiejpl_PL
dc.relation.ispartofseriesLodz University of Technology Monographsen_EN
dc.subjectapproximate pattern matchingen_EN
dc.subjectcounting filteren_EN
dc.subjectstring algorithmsen_EN
dc.subjectq-gramsen_EN
dc.subjectinversions and translocationsen_EN
dc.subjectk-differencesen_EN
dc.subjectSSEen_EN
dc.subjectprzybliżone dopasowanie do wzorcapl_PL
dc.subjectfiltr liczącypl_PL
dc.subjectalgorytmy ciągówpl_PL
dc.subjectq-gramypl_PL
dc.subjectinwersje i translokacjepl_PL
dc.subjectk-różnicepl_PL
dc.titleEngineering the counting filter for string matching algorithmsen_EN
dc.typerozdział książkipl_PL
dc.typebook chapteren_EN

Pliki

Oryginalne pliki
Teraz wyświetlane 1 - 1 z 1
Brak miniatury
Nazwa:
Engin_count_Susik_Grabowski_2016.pdf
Rozmiar:
1.88 MB
Format:
Adobe Portable Document Format
Opis:
Pobierz
Licencja
Teraz wyświetlane 1 - 1 z 1
Brak miniatury
Nazwa:
license.txt
Rozmiar:
1.71 KB
Format:
Item-specific license agreed upon to submission
Opis:
Pobierz

Kolekcje

Książki, monografie, podręczniki, rozdziały (WEEIiA)