Abstract

Suppose we have just performed searches in a self-index for two patterns $A$ and $B$ and now we want to search for their concatenation \A B); how can we best make use of our previous computations? In this paper we consider this problem and, more generally, how we can store a dynamic library of patterns that we can easily manipulate in interesting ways. We give a space- and time-efficient data structure for this problem that is compatible with many of the best self-indexes.
Original languageEnglish
Title of host publicationarXiv
Place of PublicationarXiv:1011.3491v2
Publication date2010
Publication statusSubmitted - 2010
MoE publication typeB2 Book chapter

Fields of Science

  • cs.DS

Cite this

Gagie, T., Karhu, K., Kärkkäinen, J., Mäkinen, V., & Salmela, L. (2010). Pattern Kits. Manuscript submitted for publication. In arXiv arXiv:1011.3491v2.
Gagie, Travis ; Karhu, Kalle ; Kärkkäinen, Juha ; Mäkinen, Veli ; Salmela, Leena. / Pattern Kits. arXiv. arXiv:1011.3491v2, 2010.
@inbook{3dec8b07d0cc4ba692d87ea9d8fbab96,
title = "Pattern Kits",
abstract = "Suppose we have just performed searches in a self-index for two patterns $A$ and $B$ and now we want to search for their concatenation \A B); how can we best make use of our previous computations? In this paper we consider this problem and, more generally, how we can store a dynamic library of patterns that we can easily manipulate in interesting ways. We give a space- and time-efficient data structure for this problem that is compatible with many of the best self-indexes.",
keywords = "cs.DS",
author = "Travis Gagie and Kalle Karhu and Juha K{\"a}rkk{\"a}inen and Veli M{\"a}kinen and Leena Salmela",
year = "2010",
language = "English",
booktitle = "arXiv",

}

Gagie, T, Karhu, K, Kärkkäinen, J, Mäkinen, V & Salmela, L 2010, Pattern Kits. in arXiv. arXiv:1011.3491v2.

Pattern Kits. / Gagie, Travis; Karhu, Kalle; Kärkkäinen, Juha; Mäkinen, Veli; Salmela, Leena.

arXiv. arXiv:1011.3491v2, 2010.

Research output: Chapter in Book/Report/Conference proceedingChapterScientific

TY - CHAP

T1 - Pattern Kits

AU - Gagie, Travis

AU - Karhu, Kalle

AU - Kärkkäinen, Juha

AU - Mäkinen, Veli

AU - Salmela, Leena

PY - 2010

Y1 - 2010

N2 - Suppose we have just performed searches in a self-index for two patterns $A$ and $B$ and now we want to search for their concatenation \A B); how can we best make use of our previous computations? In this paper we consider this problem and, more generally, how we can store a dynamic library of patterns that we can easily manipulate in interesting ways. We give a space- and time-efficient data structure for this problem that is compatible with many of the best self-indexes.

AB - Suppose we have just performed searches in a self-index for two patterns $A$ and $B$ and now we want to search for their concatenation \A B); how can we best make use of our previous computations? In this paper we consider this problem and, more generally, how we can store a dynamic library of patterns that we can easily manipulate in interesting ways. We give a space- and time-efficient data structure for this problem that is compatible with many of the best self-indexes.

KW - cs.DS

M3 - Chapter

BT - arXiv

CY - arXiv:1011.3491v2

ER -

Gagie T, Karhu K, Kärkkäinen J, Mäkinen V, Salmela L. Pattern Kits. In arXiv. arXiv:1011.3491v2. 2010