# Subpath Queries on Compressed Graphs: A Survey
## 3 Indexing Labeled Graphs and Regular Languages
### Hypertext Indexing  
Prior to the predominant prefix-sorting approach that we are going to discuss in detail in the next subsections, the problem of solving indexed path queries on labeled graphs has been tackled in the literature by resorting to geometric data structures [61; 62]. These solutions work in the _hypertext model_: the objects being indexed are _node-labeled_ graphs \(G=(V,E,\Sigma,\lambda)\), where function \(\lambda:V\rightarrow\Sigma^{*}\) associates a string to each node (note the difference with our edge-labeled model, where each _edge_ is labeled with a _single_ character). Let \(P=(u_{i_{1}},u_{i_{2}}),(u_{i_{2}},u_{i_{3}}),\ldots,(u_{i_{k-1}},u_{i_{k}})\) be a path in the graph spanning \(k\) (not necessarily distinct) nodes. With \(\lambda(P)\) we denote the string \(\lambda(P)=\lambda(u_{i_{1}})\cdot\lambda(u_{i_{2}})\cdots\lambda(u_{i_{k}})\). In the hypertext indexing problem, the goal is to build an index over \(G\) able to quickly support locate queries on the paths of \(G\): given a pattern \(\Pi\), determine the positions in the graph (node and starting position in the node) where an occurrence of \(\Pi\) starts. This labeled graph model is well suited for applications where the strings labeling each nodeare very long (for example, a transcriptome), in which case the label component (rather than the graph's topology) dominates the data structure's space. Both solutions discussed in Reference [61; 62] resort to geometric data structures. First, a classic text index (for example, a compressed suffix array) is built over the concatenation \(\lambda(u_{1})\cdot\#\cdots\#\cdot\lambda(u_{n})\) of the strings labeling all the graph's nodes \(u_{1},\ldots,u_{n}\). The labels are separated by a symbol \(\#\) not appearing elsewhere in order to prevent false matches. Pattern occurrences completely contained inside some \(\lambda(u_{i})\) are found using this compressed index. Then, a geometric structure is used to \"glue\" nodes connected by an edge: for each edge \((u,v)\), a two-dimensional point \((\overleftarrow{\lambda(u)},\lambda(v))\) is added to a grid as the one shown in Figure 6 (bottom left), where \(\overleftarrow{w}\) denotes the reverse of string \(w\). Again, rank space techniques are used to reduce the points \((\overleftarrow{\lambda(u)},\lambda(v))\) to integer pairs. Then, pattern occurrences spanning _one_ edge are found by issuing a four-sided geometric query for each possible pattern split as seen in Section 2.2. The main issue with these solutions is that they cannot _efficiently_ locate pattern occurrences spanning two or more edges. A tweak consists in using a seed-and-extend strategy: the pattern \(\Pi\) is split in short fragments of some length \(t\), each of which is searched separately in the index. If \(\lambda(u_{i})\geq t\) for each node \(u_{i}\), then this solution allows locating all pattern occurrences (including those spanning two or more edges). This solution, however, requires to visit the whole graph in the worst case. On realistic DNA datasets this problem is mitigated by the fact that, for large enough \(t\), the pattern's fragments of length \(t\) are \"good anchors\" and are likely to occur only within occurrences of \(\Pi\).  
As seen, hypertext indexes work well under the assumption that the strings labeling the nodes are very long. However, this assumption is often not realistic: for instance, in pan-genomics applications a single-point mutation in the genome of an individual (that is, a substitution or a small insertion/deletion) may introduce very short edges deviating from the population's reference genome. Note that here we have only discussed _indexed_ solutions. The on-line case (pattern matching on hypertext without pre-processing) has been thoroughly studied in several other works; see Reference [60; 63; 64].