A suffix tree is a compressed tree that represents all the suffixes of a given string. Such a data structure has wide applications in string processing, bioinformatics, and information retrieval and can be constructed with space/time complexity linear in the length of the string.

To reduce the space consumption further, compressed suffix trees (CSTs) make use of a “compressed suffix array, a compressed least common prefix (LCP) array, and a succinct representation of the ... topology.” Storing the topology of a CST can be done either explicitly using a balanced parentheses sequence (BPS) or implicitly using intervals in the LCP array. It seems an enhanced balanced parentheses representation (eBPR) of the LCP array works better in applications that extensively use suffix links.

According to the authors, the main contribution of the paper is “the presentation of parallel algorithms that construct succinct representations of the suffix tree topology.” The material here is well organized with adequate background and information on the problems studied. Construction of BPS and eBPR is described very well, with each topic covered in depth in an independent section. The authors assumed a parallel random access machine (PRAM) model with concurrent reads and concurrent writes.

The authors make certain strong claims. One is that their new sequential algorithm for BPS construction outperforms earlier known methods. They also declare that the methods described are currently the best, without requiring the construction of an uncompressed suffix tree topology.

All of the key ideas are demonstrated with examples and adequate references to previous literature. Detailed experimental results that support the suggested heuristics are also included. Affirmations related to the superiority of these methods can be verified by experts in the domain.

Overall, the authors have produced a very well-written paper that addresses an important problem and provides solutions that will be of interest to a broad audience of students, researchers, and practitioners.