Pattern Kits

Travis Gagie; Kalle Karhu; Juha Kärkkäinen; Veli Mäkinen; Leena Salmela

Pattern Kits

Travis Gagie, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Leena Salmela

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Scientific

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.

Translated title of the contribution	Pattern Kits
Original language	English
Title of host publication	arXiv
Place of Publication	arXiv:1011.3491v2
Publication status	Submitted - 2010
MoE publication type	B2 Book chapter

Fields of Science

cs.DS

Access to Document

pdf

http://arxiv.org/abs/1011.3491

Cite this

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

}

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 -