###
A Fast Distributed Suffix Array Generation Algorithm

####
Joćo Paulo Kitajima and Gonzalo Navarro

We present a distributed algorithm for suffix array generation,
based on the sequential algorithm of Manber and Myers. The sequential
algorithm is *O(n log n)* in the worst case and *O(n log log n)* on
average, where *n* is the text size. Using *p* processors connected
through a high bandwidth network,
we obtain *O((n/p) log log n)* average time, which is an
almost optimal speedup. Unlike previous algorithms, the text is not
transmitted through the network and hence the messages exchanged are much
smaller. We present some experimental evidence to show that the new algorithm
can be faster than the sequential Manber and Myers counterpart.