## 1 Introduction  
As a result of the sharply falling costs of sequencing, large sequence databases are rapidly emerging, and they will soon grow to thousands of genomes and more. Sequencing machines are already producing terabytes of data per day, at a few thousand dollars per genome, and will cost less very soon (see, e.g., [1]). This raises a number of challenges in bioinformatics, particularly because those sequence databases are meant to be the subject of various analysis processes that require sophisticated data structures built on them. The _suffix tree_[2; 3; 4] is probably the most important of those data structures. Many complex sequence analysis problems are solved through sophisticated traversals over the suffix tree [5]. However, a serious problem of suffix trees, aggravated on large sequence collections, is that they take much space. A naive implementation can easily require 20 bytes per character, and a very optimized one reaches 10 bytes [6]. A way to reduce this space to about 4 bytes per character is to use a simplified structure called a _suffix array_[7]. However, suffix arrays do not contain sufficient information to carry out all the complex tasks suffix trees are used for. Enhanced suffix arrays [8] extend suffix arrays so as to recover the full suffix tree functionality, raising the space to about 6 bytes per character in practice. Other heuristic space-saving methods [9] achieve about the same. For example, on DNA sequences, each character could be encoded with just 2 bits, whereas the alternatives we have considered require 32 to 160 bits per character (bpc). This is an overhead of 1600% to 8000%! The situation is also a heresy in terms of Information Theory: Whereas the information contained in a sequence of \(n\) symbols over an alphabet of size \(\sigma\) is \(n\log\sigma\) bits in the worst case, all the alternatives above require \(\Theta(n\log n)\) bits. (Our logarithms are in base 2)  
A solution to the large space requirements is of course resorting to secondary memory. However, using suffix trees on secondary memory makes them orders of magnitude slower, as most of the required traversals are highly non-local. A more interesting research direction, which has made much progress in recent years, is to design _compressed suffix trees_ (_CSTs_). Those compressed representations of suffix trees are able to approach not only the worst-case space of the sequence, but even its information content (_i.e._, they approach the space of the _compressed_ sequence). CSTs are composed of a _compressed suffix array_ (_CSA_) plus some extra information that encodes the suffix tree topology and _longest common prefix_ (_LCP_) information (more details later). The existing solutions can be divided into three categories:  
**Explicit topology**. The first CST proposal was by [PERSON] [10; 11]. It uses \(4n+o(n)\) bits to represent the suffix tree topology, plus \(2n+o(n)\) bits to represent the LCP values. In addition, it uses [PERSON]'s CSA [12], which requires \(nH_{0}+O(n\log\log\sigma)\) bits, where \(H_{0}\) is the zero-order entropy of the sequence. This structure supports most of the tree navigation operations in constant time (except, notably, going down to a child, which is an important operation), at the price of \(\Theta(n)\) bits of space on top of a CSA. **Sampling**. A second proposal was by [PERSON] _et al_. [13; 14]. It is based on sampling some suffix tree nodes and recovering the information on any other node by moving to the nearest sample using suffix links. It requires only \(o(n)\) bits on top of a CSA. By using an FM-index [15] as the CSA, one achieves \(nH_{k}+o(n\log\sigma)\) bits of space, where \(H_{k}\) is the \(k\)-th order empirical entropy of the sequence (a measure of statistical compressibility [16]), for sufficiently low \(k\leq\alpha\log_{\sigma}n\), for any constant \(0<\alpha<1\). The navigation operations are supported in polylogarithmic time (at best \(\Theta(\log n\log\log n)\) in their paper). **Intervals**. Yet a third proposal was by [PERSON] _et al_.