Title :
A fast distributed suffix array generation algorithm
Author :
Kitajima, João Paulo ; Navarro, Gonzalo
Author_Institution :
Bioinf. Lab., Univ. Estadual de Campinas, Sao Paulo, Brazil
Abstract :
We present a distributed algorithm for suffix array generation, based on the sequential algorithm of U. Manber and E. Myers (1993). The sequential algorithm is O(nlogn) in the worst case and O(nloglogn) on average, where n is the text size. Using p processors connected through a high bandwidth network, we obtain O((n/p)loglogn) 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 & Myers counterpart
Keywords :
computational complexity; database management systems; distributed algorithms; indexing; text analysis; almost optimal speedup; average time; fast distributed suffix array generation algorithm; high bandwidth network; message exchange; previous algorithms; sequential algorithm; text size; worst case; Bandwidth; Distributed algorithms;
Conference_Titel :
String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware
Conference_Location :
Cancun
Print_ISBN :
0-7695-0268-7
DOI :
10.1109/SPIRE.1999.796583