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.

关键词： suffix tree parallel suffix tree algorithm string matching parallel algorithm

作者: Bing Zhang Zhenglin Huang

作者单位: College of Computer and Software Shenzhen University Shenzhen, China

会议类型: 国际会议

会议名称: 2011 International Conference on Information and Computer Networks(ICICN 2011)(2011年信息与计算机网络国际会议)

会议地点: 贵阳

会议语种:英文

页码: 143-147

在线出版日期: 2011-01-26（万方平台首次上网日期，不代表论文的发表时间）