Fast Indexes for Gapped Pattern Matching

Manuel Cáceres; Simon Puglisi; Bella Zhukova

doi:10.1007/978-3-030-38919-2_40

Fast Indexes for Gapped Pattern Matching

Manuel Cáceres, Simon Puglisi, Bella Zhukova

Research output: Conference materials › Paper

Abstract

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.

Original language	English
Pages	493-504
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-030-38919-2_40
Publication status	Published - 17 Jan 2020
MoE publication type	Not Eligible
Event	SOFSEM: 46th International Conference on Current Trends in Theory and Practice of Computer Science - Limassol, Cyprus Duration: 21 Jan 2020 → 24 Jan 2020 Conference number: 46 http://cyprusconferences.org/sofsem2020/

Conference

Conference	SOFSEM
Abbreviated title	SOFSEM
Country	Cyprus
City	Limassol
Period	21/01/2020 → 24/01/2020
Internet address	http://cyprusconferences.org/sofsem2020/

Fields of Science

113 Computer and information sciences
Pattern matching with gaps

Access to Document

10.1007/978-3-030-38919-2_40

Cite this

Cáceres, M., Puglisi, S., & Zhukova, B. (2020). Fast Indexes for Gapped Pattern Matching. 493-504. Paper presented at SOFSEM, Limassol, Cyprus. https://doi.org/10.1007/978-3-030-38919-2_40

@conference{699ec769ab11486eb9c36feb17570ccf,

title = "Fast Indexes for Gapped Pattern Matching",

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

keywords = "113 Computer and information sciences, Pattern matching with gaps",

author = "Manuel C{\'a}ceres and Simon Puglisi and Bella Zhukova",

year = "2020",

month = "1",

day = "17",

doi = "10.1007/978-3-030-38919-2_40",

language = "English",

pages = "493--504",

note = "SOFSEM : 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM ; Conference date: 21-01-2020 Through 24-01-2020",

url = "http://cyprusconferences.org/sofsem2020/",

}

TY - CONF

T1 - Fast Indexes for Gapped Pattern Matching

AU - Cáceres, Manuel

AU - Puglisi, Simon

AU - Zhukova, Bella

PY - 2020/1/17

Y1 - 2020/1/17

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

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

KW - 113 Computer and information sciences

KW - Pattern matching with gaps

U2 - 10.1007/978-3-030-38919-2_40

DO - 10.1007/978-3-030-38919-2_40

M3 - Paper

SP - 493

EP - 504

ER -