# Subpath Queries on Compressed Graphs: A Survey
## 1 Introduction
### The Repetitive Model  
Since their introduction in the year 2000, entropy-compressed text indexes have had a dramatic impact in domains, such as bioinformatics; the most widely used DNA aligners, Bowtie [21] and BWA [22], are based on compressed indexes and can align thousands of short DNA fragments per second on large genomes while using only compressed space in RAM during execution. As seen in the previous section, these indexes operate within a space bounded by the text's empirical entropy [16; 17]. Entropy, however, is insensitive to long repetitions: the entropy-compressed version of \(\mathcal{T}\cdot\mathcal{T}\) (that is, text \(\mathcal{T}\) concatenated with itself) takes at least twice the space of the entropy-compressed \(\mathcal{T}\)[23]. There is a simple reason for this fact: by its very definition (see Section 2.1), the quantity \(H_{0}\) depends only on the characters' relative frequencies in the text. Since characters in \(\mathcal{T}\) and \(\mathcal{T}\cdot\mathcal{T}\) have the same relative frequencies, it follows that their entropies are the same. The claim follows, being the length of \(\mathcal{T}\cdot\mathcal{T}\) twice the length of \(\mathcal{T}\). While the above reasoning might seem artificial, the same problem arises on texts composed of large repetitions. Today, most large data sources, such as DNA sequencers and the web, follow this new model of _highly repetitive data_. As a consequence, entropy-compressed text indexes are no longer able to keep pace with the exponentially-increasing rate at which this data is produced, as very often the mere index size exceeds the RAM limit. For this reason, in recent years more powerful compressed indexes have emerged; these  
Figure 5: Compressed Suffix Array (CSA): we store the delta-encoded \(\psi\) and the first letter (underlined) of each suffix (array F). are based on the Lempel-Ziv factorization [23], the run-length Burrows-Wheeler Transform (BWT) [24; 25; 26], context-free grammars [27], string attractors [28; 29] (combinatorial objects generalizing those compressors), and more abstract measures of repetitiveness [30]. The core idea behind these indexes (with the exception of the run-length BWT; see Section 3) is to partition the text into phrases that occur also elsewhere and to use _geometric_ data structures to locate pattern occurrences. To get a more detailed intuition of how these indexes work, consider the Lempel-Ziv\({}^{\prime}\)78 (LZ78) compression scheme. The LZ78 factorization breaks the text into phrases with the property that each phrase extends by one character a previous phrase; see the example in Figure 6 (top). The mechanism we are going to describe works for any factorization-based compressor (also called _dictionary compressors_). A factorization-based index keeps a two-dimensional geometric data structure storing a labeled point \((x,y,\ell)\) for each phrase \(y\), where \(x\) is the reversed text prefix preceding the phrase and \(\ell\) is the first text position of the phrase. Efficient techniques not discussed here (in particular, mapping to _rank space_) exist to opportunely reduce \(x\) and \(y\) to small integers preserving the lexicographic order of the corresponding strings (see, for example, [PERSON] and [PERSON] [23]). For example, such a point in Figure 6 is \((GCA,CG,4)\), corresponding to the phrase break between positions 3 and 4. To understand how _locate_ queries are answered, consider the pattern \(\Pi=CAC\). All occurrences of \(\Pi\) crossing a phrase boundary can be split into a prefix and a suffix, aligned on the phrase boundary. Let us consider the split \(CA|C\) (all possible splits have to be considered for the following algorithm to be complete). If \(\Pi\) occurs in \(\mathcal{T}\) with this split, then \(C\) will be a prefix of some phrase \(y\), and \(CA\) will be a suffix of the text prefix preceding \(y\). We can find all phrases \(y\) with this property by issuing a four-sided range query on our grid as shown in Figure 6 (bottom left).