Relative FM-indexes

Djamal Belazzougui; Travis Gagie; Simon Gog; Giovanni Manzini; Jouni Sirén

doi:10.1007/978-3-319-11918-2

Relative FM-indexes

Djamal Belazzougui
, Travis Gagie
, Simon Gog
, Giovanni Manzini
, Jouni Sirén

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Intuitively, if two strings S₁ and S₂ are sufficiently similar and we already have an FM-index for S₁ then, by storing a little extra information, we should be able to reuse parts of that index in an FM-index for S₂. We formalize this intuition and show that it can lead to significant space savings in practice, as well as to some interesting theoretical problems.

Original language	English
Title of host publication	String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings
Editors	Edleno Moura, Maxime Crochemore
Publisher	Springer Verlag
Pages	52-64
Number of pages	13
ISBN (Electronic)	9783319119175
DOIs	https://doi.org/10.1007/978-3-319-11918-2
Publication status	Published - 2014
Externally published	Yes
Event	21st International Symposium on String Processing and Information Retrieval, SPIRE 2014 - Ouro Preto, Brazil Duration: 20 Oct 2014 → 22 Oct 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8799
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Symposium on String Processing and Information Retrieval, SPIRE 2014
Country/Territory	Brazil
City	Ouro Preto
Period	20/10/14 → 22/10/14

Access to Document

10.1007/978-3-319-11918-2

Cite this

Belazzougui, D., Gagie, T., Gog, S., Manzini, G., & Sirén, J. (2014). Relative FM-indexes. In E. Moura, & M. Crochemore (Eds.), String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings (pp. 52-64). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8799). Springer Verlag. https://doi.org/10.1007/978-3-319-11918-2

Belazzougui, Djamal ; Gagie, Travis ; Gog, Simon et al. / Relative FM-indexes. String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings. editor / Edleno Moura ; Maxime Crochemore. Springer Verlag, 2014. pp. 52-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5931be73f2a64ed78c6d67eba9a7f5eb,

title = "Relative FM-indexes",

abstract = "Intuitively, if two strings S1 and S2 are sufficiently similar and we already have an FM-index for S1 then, by storing a little extra information, we should be able to reuse parts of that index in an FM-index for S2. We formalize this intuition and show that it can lead to significant space savings in practice, as well as to some interesting theoretical problems.",

author = "Djamal Belazzougui and Travis Gagie and Simon Gog and Giovanni Manzini and Jouni Sir{\'e}n",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.; 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014 ; Conference date: 20-10-2014 Through 22-10-2014",

year = "2014",

doi = "10.1007/978-3-319-11918-2",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "52--64",

editor = "Edleno Moura and Maxime Crochemore",

booktitle = "String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings",

address = "Germany",

}

Belazzougui, D, Gagie, T, Gog, S, Manzini, G & Sirén, J 2014, Relative FM-indexes. in E Moura & M Crochemore (eds), String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8799, Springer Verlag, pp. 52-64, 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014, Ouro Preto, Brazil, 20/10/14. https://doi.org/10.1007/978-3-319-11918-2

Relative FM-indexes. / Belazzougui, Djamal; Gagie, Travis; Gog, Simon et al.
String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings. ed. / Edleno Moura; Maxime Crochemore. Springer Verlag, 2014. p. 52-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8799).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Relative FM-indexes

AU - Belazzougui, Djamal

AU - Gagie, Travis

AU - Gog, Simon

AU - Manzini, Giovanni

AU - Sirén, Jouni

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - Intuitively, if two strings S1 and S2 are sufficiently similar and we already have an FM-index for S1 then, by storing a little extra information, we should be able to reuse parts of that index in an FM-index for S2. We formalize this intuition and show that it can lead to significant space savings in practice, as well as to some interesting theoretical problems.

AB - Intuitively, if two strings S1 and S2 are sufficiently similar and we already have an FM-index for S1 then, by storing a little extra information, we should be able to reuse parts of that index in an FM-index for S2. We formalize this intuition and show that it can lead to significant space savings in practice, as well as to some interesting theoretical problems.

UR - https://www.scopus.com/pages/publications/84908701491

U2 - 10.1007/978-3-319-11918-2

DO - 10.1007/978-3-319-11918-2

M3 - Conference contribution

AN - SCOPUS:84908701491

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 52

EP - 64

BT - String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings

A2 - Moura, Edleno

A2 - Crochemore, Maxime

PB - Springer Verlag

T2 - 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014

Y2 - 20 October 2014 through 22 October 2014

ER -

Belazzougui D, Gagie T, Gog S, Manzini G, Sirén J. Relative FM-indexes. In Moura E, Crochemore M, editors, String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings. Springer Verlag. 2014. p. 52-64. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-11918-2

Relative FM-indexes

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this