License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.17
URN: urn:nbn:de:0030-drops-76116
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7611/
Go to the corresponding LIPIcs Volume Portal

Kärkkäinen, Juha ; Kempa, Dominik

Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet

pdf-format:
LIPIcs-SEA-2017-17.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{krkkinen_et_al:LIPIcs:2017:7611,
  author =	{Juha K{\"a}rkk{\"a}inen and Dominik Kempa},
  title =	{{Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7611},
  URN =		{urn:nbn:de:0030-drops-76116},
  doi =		{10.4230/LIPIcs.SEA.2017.17},
  annote =	{Keywords: LCP array, suffix array, external memory algorithms}
}

Keywords: LCP array, suffix array, external memory algorithms
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI