Lightweight data indexing and compression in external memory

Paolo Ferragina, Travis Gagie, Giovanni Manzini

Risultato della ricerca: Contributo su rivistaArticolo in rivistapeer review

Abstract

In this paper we describe algorithms for computing the Burrows-Wheeler Transform (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 working space on disk while all previous approaches use Θ(nlog n) bits. This is achieved by building the bwt directly without passing through the construction of the Suffix Array/Tree data structure. 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: internalmemory space × number of passes over the disk data, showing that our algorithms are within an O(log n) factor of the optimal.

Lingua originaleInglese
pagine (da-a)707-730
Numero di pagine24
RivistaAlgorithmica
Volume63
Numero di pubblicazione3
DOI
Stato di pubblicazionePubblicato - lug 2012
Pubblicato esternamente

Fingerprint

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

Cita questo