Massively Parallel Suffix Array Construction
by Costas S. Iliopoulos and Maureen Korda

Abstract:

This paper considers the construction of the suffix
array of a string on the MasPar MP-2 architecture. Suffix arrays are
space-efficient variants of the suffix trees, a fundamental dictionary data
structure that is the backbone of many string algorithms for pattern
matching and textual information retreival.  We adapt known
PRAM techniques for implementation on the MasPar: bulletin boards,
doubling techniques and sorting methods. Performance results are presented.