Engineering a lightweight external memory suffix array construction algorithm (Q2363989): Difference between revisions

In this article, the authors show how to use delayed merging to reduce from \(O (n^2 / (M B))\) blocks to \(O (n^2 / (M B \log_\sigma n) + n / B)\) blocks the I/O complexity of Ferragina et al.'s scan-based external-memory suffix-array construction, where \(n\) is the length of the text, \(M\) is the size of RAM in words, \(B\) is the size of a block in words and \(\sigma\) is the alphabet size. They also show how to apply techniques developed since the publication of Ferragina et al.'s algorithm, to reduce the running time from \(O((n^2 / M) \log \sigma)\) to \(O ((n^2 / M) \log (\log (\sigma) / \log \log n)\). Finally, they show experimentally that their algorithm is competitive with what was the state of the art when this article was submitted. While it was in press, however, several new algorithms were developed, and the authors et al.'s paper [``Engineering external memory induced suffix sorting'', in: Proceedings of the 19th workshop on algorithm engineering and experiments, Alenex'17. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 98--108 (2017; \url{doi:10.1137/1.9781611974768.8})] is probably now a better reference for most purposes.