Florian Kurpicz
Presentation at ALENEX 2019

Lightweight Distributed Suffix Array Construction

Today, I presented our results on distributed suffix array construction, i.e., distributed suffix sorting. In addition to a novel distributed suffix sorting algorithm, we present the (to our best knowledge) first implementation of a distributed string sorting algorithm. The slides are available as handout and heavily animated. The paper is available here (DOI).

Slides in Handout Mode

Slide image alenex_2019_slides_handout-01.jpg
Slide image alenex_2019_slides_handout-02.jpg
Slide image alenex_2019_slides_handout-03.jpg
Slide image alenex_2019_slides_handout-04.jpg
Slide image alenex_2019_slides_handout-05.jpg
Slide image alenex_2019_slides_handout-06.jpg
Slide image alenex_2019_slides_handout-07.jpg
Slide image alenex_2019_slides_handout-08.jpg
Slide image alenex_2019_slides_handout-09.jpg
Slide image alenex_2019_slides_handout-10.jpg
Slide image alenex_2019_slides_handout-11.jpg
Slide image alenex_2019_slides_handout-12.jpg
Slide image alenex_2019_slides_handout-13.jpg
Slide image alenex_2019_slides_handout-14.jpg
Slide image alenex_2019_slides_handout-15.jpg
Slide image alenex_2019_slides_handout-16.jpg
Slide image alenex_2019_slides_handout-17.jpg
Slide image alenex_2019_slides_handout-18.jpg
Slide image alenex_2019_slides_handout-19.jpg
Slide image alenex_2019_slides_handout-20.jpg
Slide image alenex_2019_slides_handout-21.jpg
Slide image alenex_2019_slides_handout-22.jpg
Slide image alenex_2019_slides_handout-23.jpg

Abstract

We present two new distributed suffix array construction algorithms. One of our algorithms requires only half as much memory as its competitor (PSAC) [Flick & Aluru, SC 2015], while achieving similar speed. In practice, we can compute on the same hardware suffix arrays for text twice as large as PSAC. The other algorithm still requires less memory than PSAC but is faster on some instances. As a by-product, we also engineered the first distributed string sorting algorithm. All of our algorithms are tested on text collections of up to 115 GB and running on 1280 cores.