Fast relative Lempel-Ziv self-index for similar sequences

Huy Hoang Do, Jesper Andreas Jansson, Kunihiko Sadakane, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

14 Citations (Scopus)

Abstract

Recent advances in biotechnology and web technology are generating huge collections of similar strings. People now face the problem of storing them compactly while supporting fast pattern searching. One compression scheme called relative Lempel-Ziv compression uses textual substitutions from a reference text as follows: Given a (large) set S of strings, represent each string in S as a concatenation of substrings from a reference string R. This basic scheme gives a good compression ratio when every string in S is similar to R, but does not provide any pattern searching functionality. Here, we describe a new data structure that supports fast pattern searching.
Original languageEnglish
Title of host publicationFrontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings
Pages291-302
Number of pages12
DOIs
Publication statusPublished - 23 May 2012
Externally publishedYes
Event6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012 - Beijing, China
Duration: 14 May 201216 May 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7285 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012
CountryChina
CityBeijing
Period14/05/1216/05/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this