@inproceedings{228bd84ecf78401dacbce8a07e4ecc34,
title = "Slashing the time for BWT inversion",
abstract = "Inverting the Burrows-Wheeler transform (BWT) is a bottleneck in BWT-based decompressors. The state-of-the-art inversion algorithm runs in linear time but is slow in practice due to CPU-cache misses. For more than a decade these cache misses have been thought to be inherent to BWT inversion. We show how to reduce the number of cache misses by a factor of nearly two, and simultaneously the cost of cache misses by another factor of two, obtaining a consistent speed up by a factor of 2.3-4. We can do even better if the data is highly repetitive. We describe an algorithm that achieves an asymptotic reduction in cache misses in theory and is the fastest algorithm in practice for such data.",
author = "Juha K{\"a}rkk{\"a}inen and Dominik Kempa and Puglisi, \{Simon J.\}",
year = "2012",
doi = "10.1109/DCC.2012.18",
language = "English",
isbn = "9780769546568",
series = "Data Compression Conference Proceedings",
pages = "99--108",
booktitle = "Proceedings - DCC 2012",
note = "2012 Data Compression Conference, DCC 2012 ; Conference date: 10-04-2012 Through 12-04-2012",
}