Lightweight data indexing and compression in external memory

Paolo Ferragina, Travis Gagie, Giovanni Manzini

Risultato della ricerca: Capitolo in libro/report/atti di convegnoContributo a conferenzapeer review

Abstract

In this paper we describe algorithms for computing the BWT and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size n, they use only n bits of disk working space while all previous approaches use Θ(n logn) bits of disk working space. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses. We also present a scan-based algorithm for inverting the BWT that uses Θ(n) bits of working space, and a lightweight internal-memory algorithm for computing the BWT which is the fastest in the literature when the available working space is o(n) bits. Finally, we prove lower bounds on the complexity of computing and inverting the BWT via sequential scans in terms of the classic product: internal-memory space × number of passes over the disk data, showing that our algorithms are within an O(logn) factor of the optimal.

Lingua originaleInglese
Titolo della pubblicazione ospiteLATIN 2010
Sottotitolo della pubblicazione ospiteTheoretical Informatics - 9th Latin American Symposium, Proceedings
Pagine697-710
Numero di pagine14
DOI
Stato di pubblicazionePubblicato - 2010
Pubblicato esternamente
Evento9th Latin American Theoretical Informatics Symposium, LATIN 2010 - Oaxaca, Mexico
Durata: 19 apr 201023 apr 2010

Serie di pubblicazioni

NomeLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6034 LNCS
ISSN (stampa)0302-9743
ISSN (elettronico)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???9th Latin American Theoretical Informatics Symposium, LATIN 2010
Paese/TerritorioMexico
CittàOaxaca
Periodo19/04/1023/04/10

Fingerprint

Entra nei temi di ricerca di 'Lightweight data indexing and compression in external memory'. Insieme formano una fingerprint unica.

Cita questo