2026-08-17T16:56:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18642 2024-03-06T11:02:20Z ddc:004 open_access

Fast, Parallel, and Cache-Friendly Suffix Array Construction Khan, Jamshed Rubel, Tobias Dhulipala, Laxman Molloy, Erin Patro, Rob Suffix Array Longest Common Prefix Data Structures Indexing Parallel Algorithms String indexes such as the suffix array (SA) and the closely related longest common prefix (LCP) array are fundamental objects in bioinformatics and have a wide variety of applications. Despite their importance in practice, few scalable parallel algorithms for constructing these are known, and the existing algorithms can be highly non-trivial to implement and parallelize. In this paper we present CaPS-SA, a simple and scalable parallel algorithm for constructing these string indexes inspired by samplesort. Due to its design, CaPS-SA has excellent memory-locality and thus incurs fewer cache misses and achieves strong performance on modern multicore systems with deep cache hierarchies. We show that despite its simple design, CaPS-SA outperforms existing state-of-the-art parallel SA and LCP-array construction algorithms on modern hardware. Finally, motivated by applications in modern aligners where the query strings have bounded lengths, we introduce the notion of a bounded-context SA and show that CaPS-SA can easily be extended to exploit this structure to obtain further speedups. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jamshed Khan and Tobias Rubel and Laxman Dhulipala and Erin Molloy and Rob Patro 2023 Is Part Of LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2023.16 urn:nbn:de:0030-drops-186424 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.16 eng https://creativecommons.org/licenses/by/4.0/legalcode