2026-07-22T16:12:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24515 2025-12-16T14:00:14Z ddc:004 open_access

Fast and Lightweight Distributed Suffix Array Construction Haag, Manuel Kurpicz, Florian Sanders, Peter Schimek, Matthias Distributed Computing Suffix Array Construction The suffix array contains the lexicographical order of all suffixes of a text. It is one of the most well-studied text indices with applications in bioinformatics, compression, and pattern matching. The main bottleneck of distributed-memory suffix array construction algorithms is their memory requirements. Even careful implementations require 30×-60× the input size as working memory. We present a scalable and lightweight distributed-memory adaptation of the difference cover (DCX) suffix array construction algorithm. Our approach relies on novel bucketing and random chunk redistribution techniques which reduce our memory requirement to 20×-26× the input size for medium-sized inputs and to 14×-15× for large-sized inputs. Regarding running time, we achieve speedups of up to 5× over current state-of-the-art distributed suffix array construction algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Haag and Florian Kurpicz and Peter Sanders and Matthias Schimek 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.47 urn:nbn:de:0030-drops-245154 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.47 eng https://creativecommons.org/licenses/by/4.0/legalcode