Fast Indexes for Gapped Pattern Matching

Manuel Cáceres, Simon Puglisi, Bella Zhukova

Tutkimustuotos: KonferenssimateriaalitKonferenssiesitysvertaisarvioitu

Abstrakti

We describe indexes for searching large data sets for variable-length-gapped (VLG) patterns. VLG patterns are composed of two or more subpatterns, between each adjacent pair of which is a gap-constraint specifying upper and lower bounds on the distance allowed between sub-patterns. VLG patterns have numerous applications in computational biology (motif search), information retrieval (e.g., for language models, snippet generation, machine translation) and capture a useful subclass of the regular expressions commonly used in practice for searching source code. Our best approach provides search speeds several times faster than prior art across a broad range of patterns and texts.
Alkuperäiskielienglanti
Sivut493-504
Sivumäärä12
DOI - pysyväislinkit
TilaJulkaistu - 17 tammikuuta 2020
OKM-julkaisutyyppiEi sovellu
TapahtumaSOFSEM: 46th International Conference on Current Trends in Theory and Practice of Computer Science - Limassol, Kypros
Kesto: 21 tammikuuta 202024 tammikuuta 2020
Konferenssinumero: 46
http://cyprusconferences.org/sofsem2020/

Konferenssi

KonferenssiSOFSEM
LyhennettäSOFSEM
MaaKypros
KaupunkiLimassol
Ajanjakso21/01/202024/01/2020
www-osoite

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä