Prague Stringology Conference 2013

Matthew Felice Pace and Alexander Tiskin

Parallel Suffix Array Construction by Accelerated Sampling

Abstract:
A deterministic BSP algorithm for constructing the suffix array of a given string is presented, based on a technique that we call accelerated sampling. It runs in optimal O(
n
p
) local computation and communication, and requires a near optimal O(log log p) supersteps. The algorithm provides an improvement over the synchronisation costs of existing algorithms, and reinforces the importance of the sampling technique.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation