Optimal Parallel Suffix Tree Construction

✍ Scribed by Ramesh Hariharan

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 656 KB
• Volume: 55
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1997.1496

✦ Synopsis

An O(m)-work, O(m)-space, O(log 4 m)-time CREW-PRAM algorithm for constructing the suffix tree of a string s of length m drawn from any fixed alphabet set is obtained. This is the first known work and space optimal parallel algorithm for this problem. It can be generalized to a string s drawn from any general alphabet set to perform in O(log 4 m) time and O(m log |7| ) work and space, after the characters in s have been sorted alphabetically, where |7| is the number of distinct characters in s. In this case too, the algorithm is work-optimal.