## 7 Practical Issues and Testing
Although in theory this process could slow down our algorithm by a factor of \(O(\log k)\), in practice this factor was negligible. We used the texts from the Pizza&Chili corpus ([[http://pizzachili.dcc.uchile.cl](http://pizzachili.dcc.uchile.cl)]([http://pizzachili.dcc.uchile.cl](http://pizzachili.dcc.uchile.cl))), with 50 MB of English and DNA and 64 MB of proteins. The machine was a Pentium 4, 3.2 GHz, 1 MB L2 cache, 1 GB RAM, running Fedora Core 3, and compiling with gcc-3.4 -09. The pattern strings were sampled randomly from the text and each character was distorted with \(10\%\) of probability. All the patterns had length \(m=30\). Every configuration was tested during at least 60 seconds using at least 5 repetitions. Hence the numbers of repetitions varied between 5 and 130,000. To parametrize the hybrid index we tested all the \(j\) values from 1 to \(k+1\) and reported the best time. To parametrize we choose \(q=\lfloor m/h\rfloor\) and \(s=\lfloor k/h\rfloor+1\) for some convenient \(h\), since we can prove that this is the best approach and it was corroborated by our experiments. To determine the value of \(h\) and \(v\) we also tested the viable configurations and reported the best results. In our examples choosing \(v\) and \(h\) such that \(2v\) is slightly smaller than \(q\) yielded the best configuration. Figure 9 shows the sensitivity of the ILZI to this parameter. The LZI and DLZI are not parametrized. The average query time, in seconds, is shown in Figure 8, and the respective memory heap peaks for indexed approaches are shown in Table 1. The hybrid index provides the fastest approach to the problem. However it also requires the most space. Aside from the hybrid index the ILZI is always either the fastest or within reasonable distance from the fastest approach. For low error level, \(k=1\) or \(k=2\), the ILZI is significantly faster, up to an order of magnitude better. This is very important since this is the area where indexed ASM has chances to make a difference. The sequential approaches outperform all compressed indexing approaches for sufficiently high error levels. In DNA this occurs at \(k=4\) and in English at \(k=5\). Figure 8: Average user time for finding the occurrences of patterns of size 30 with \(k\) errors in DNA, English, and Proteins. The \(y\) axis units are in seconds. Figure 9: Average user time, in seconds, that the ILZI takes to find occurrences of patterns of size 30 with \(k\) errors, using different \(v\)’s. The ILZI performed particularly well on proteins, as did the hybrid index. This could be due to the fact that proteins behave closer to random text, and this means that the parametrization of ours and the hybrid index indeed balances between exponential worst cases. In terms of space the ILZI is also very competitive, as it occupies almost the same space as the plain text, except for proteins. We presented the space that the algorithms need to operate and not just the index size, since the other approaches build intermediate data structures at search time. Our BiFMI index, on the other hand, achieves the smallest space. We maintain a sparse sampling for our prototype, to show that even within little space we can achieve competitive performance. The FMIIndex, on the other hand, needs a much denser sampling to be competitive. Thus our hierarchical and bidirectional verification method is faster than the basic one, even if run on a much slower index. The performance of the BiFMI prototype closely follows that of ILZI, except for the DNA file. This indicates that it was able to approach hybrid performance in minimal space. It is also, mostly, capable of reducing the gap caused by cache misses. Among the exact partitioning indexes, the DLZI obtained the best performance. Although it is in some cases the fastest when we exclude Hybrid, in general the compressed hybrid approaches achieved the same or better performance using much less space.