A new parallel suffix tree construction algorithm

A parallel suffix tree construction algorithm is presented. The suffix tree is decomposed into many sub-suffix trees according to characters of the string to be suffixed, each of which is a suffix tree starting with a specific character. Theoretic prove is given to show that the proposed decomposition scheme is correct and the decomposed sub-suffix trees can be constructed in parallel on multiple node computers in a distributed system. The workload of generating a suffix tree is almost evenly distributed among many nodes in the distributed system, and both the time and space cost is greatly reduced. Moreover, once sub-suffix trees are constructed on each node, multiple keywords starting with different characters can be searched in parallel on the node computers. Comparison results on suffix tree generating cost and keyword string matching performance show that the presented suffix tree algorithm is better in terms of time complexity on both construction and matching.