Parallel Construction of Suffix Trees
后缀树的并行构造算法

The suffix tree is a very important data structure, which finds a wide variety of applications in many areas related to string processing. While using suffix trees, how to construct the suffix trees efficiently is the key problem. The serial suffix tree construction algorithms available now can run in linear time and space, however, when the string is too long, the time and space consumption is still unendurable, which greatly restricts the employability of suffix trees. While, parallelism seems to be a good way to solve the problem, so some researchers present parallel construction algorithms of suffix trees. In this paper, we survey three kinds of parallel construction algorithms of suffix trees and give them a detailed comparison. Also, we point out the remaining problems and research directions in this area.