@inproceedings{d6fc89a8d7fb4bc9840ef60abf3160c5,
title = "Engineering external memory LCP array construction: Parallel, in-place and large alphabet",
abstract = "The suffix array augmented with the LCP array is perhaps the most important data structure in modern string processing. There has been a lot of recent research activity on constructing these arrays in external memory. In this paper, we engineer the two fastest LCP array construction algorithms (ESA 2016) and improve them in three ways. First, we speed up the algorithms by up to a factor of two through parallelism. Just 8 threads is sufficient for making the algorithms essentially I/O bound. Second, we reduce the disk space usage of the algorithms making them in-place: The input (text and suffix array) is treated as read-only and the working disk space never exceeds the size of the final output (the LCP array). Third, we add support for large alphabets. All previous implementations assume the byte alphabet.",
keywords = "External memory algorithms, LCP array, Suffix array",
author = "Juha Karkkainen and Dominik Kempa",
note = "Publisher Copyright: {\textcopyright} Juha K{\"a}rkk{\"a}inen and Dominik Kempa.; 16th Symposium on Experimental Algorithms, SEA 2017 ; Conference date: 21-06-2017 Through 23-06-2017",
year = "2017",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.SEA.2017.17",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Puglisi, \{Simon J.\} and Pissis, \{Solon P.\} and Rajeev Raman and Iliopoulos, \{Costas S.\}",
booktitle = "16th Symposium on Experimental Algorithms, SEA 2017",
}