TY - GEN
T1 - Lightweight data indexing and compression in external memory
AU - Ferragina, Paolo
AU - Gagie, Travis
AU - Manzini, Giovanni
N1 - Funding Information:
The first author has been partially supported by Yahoo! Research and FIRB Linguistica 2006. The second author has been partially funded by Millennium Institute for Cell Dynamics and Biotechnology (ICDB), Grant ICM P05-001-F, Mideplan, Chile.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77953507125&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-12200-2_60
DO - 10.1007/978-3-642-12200-2_60
M3 - Conference contribution
AN - SCOPUS:77953507125
SN - 3642121993
SN - 9783642121999
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 697
EP - 710
BT - LATIN 2010
T2 - 9th Latin American Theoretical Informatics Symposium, LATIN 2010
Y2 - 19 April 2010 through 23 April 2010
ER -