1. Fast, Parallel, and Cache-Friendly Suffix Array Construction
- Author
-
Jamshed Khan and Tobias Rubel and Laxman Dhulipala and Erin Molloy and Rob Patro, Khan, Jamshed, Rubel, Tobias, Dhulipala, Laxman, Molloy, Erin, Patro, Rob, Jamshed Khan and Tobias Rubel and Laxman Dhulipala and Erin Molloy and Rob Patro, Khan, Jamshed, Rubel, Tobias, Dhulipala, Laxman, Molloy, Erin, and Patro, Rob
- Abstract
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.
- Published
- 2023
- Full Text
- View/download PDF