The compressed suffix tree (CST) supports a number of search algorithms that run in the order of the query length irrespective of the size of the corpus which i

The compressed suffix tree (CST) supports a number of search algorithms that run in the order of the query length irrespective of the size of the corpus which is being searched. That the suffix tree is compressed allows it use space that is often not much larger than the input sequence, and this effect is improved in the case of inputs with internal repetitions, which seems to be the norm in the case of naturally-arising data (i.e. almost anywhere that Zipf's law holds). As the authors point out, existing algorithms for the construction of the compressed suffix tree require space that is proportional to the alphabet size. When we work with limited alphabets, like DNA, this factor is small and we tend to not worry about it. Many real-world data sets do have larger alphabet sizes, and so there is a need to efficiently generate the CST for them. Removing the alphabet-size bound on the space required for construction is a big deal. Existing methods require huge amounts of space to construct the CST or CSA (compressed suffix array) for large alphabets, and are barely practical to use. In practice results of this kind have proceeded implementations that are usable by a year or more. Libraries like sdsl-lite have accelerated the rate at which implementations get into the hands of compressed data structure researchers in much the same way that R did for statistical models, so hopefully we can see benefits of this result sooner. Unfortunately, it will take a deeper reading of the paper by someone who is more intimately involved in this research to be able to describe exactly why this result may not be practical. A quick read does not suggest any obvious problems, the authors have a good track record and are very positive about many follow-on results (see conclusions).