Transformation of Suffix Arrays into Suffix Trees on the MPI Environment

摘要

Suffix trees and suffix arrays are two well-known index data structures for strings. It is known that the latter can be easily transformed into the former: Iliopoulos and Rytter [5] showed two simple transformation algorithms on the CREW PRAM model. However, the PRAM model is a theoretical one and we need a practical parallel model. The Message Passing Interface (MPI) is a standard widely used on both massively parallel machines and on clusters. In this paper, we show how to implement the algorithms of Iliopoulos and Rytter on the MPI environment. Our contribution includes the modification of algorithms due to the lack of shared memory, small number of processors, communication costs between processors.