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.