Experimental Analysis of Parallel Quicksort-Based Algorithm for Suffix Array Generation

Autran Macźdo, Marco Cristo, Elaine Silva, Denilson Barbosa, Joćo Paulo Kitajima, Berthier Ribeiro, Gonzalo Navarro and Nivio Ziviani

This paper presents experiments performed with an implementation of a quicksort-based parallel indexing algorithm. Besides the expected reduction in execution time, it was observed that the word frequency distribution of the input textual database has a strong influence on performance. Communication and computational load balances are achieved by processing the same quantity of text on each processor. This effectively occurs due to the auto-similar feature of tests, verified experimentally in this work. Also, as seen by the experiments, the auto-similarity of the word frequency distribution implies that the distribution is independent of the text size. In terms of implementation, the knowledge a priori of this word frequency may improve the indexing time by eliminating certain parts of the algorithm.