# siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves
## 7 Experiments  
We evaluated the performance of siEDM on one core of a quad-core Intel Xeon Processor E5540 (2.53 GHz) machine with 144 GB memory. We implemented siEDM using the rank/select dictionary and GMR in libcds ([[https://github.com/fclaude/libcds](https://github.com/fclaude/libcds)]([https://github.com/fclaude/libcds](https://github.com/fclaude/libcds))). We used two standard benchmark datasets of einstein and cere from repetitive text collections in the pizza and chili corpus ([[http://pizzachili.dcc.uchile.cl/repc](http://pizzachili.dcc.uchile.cl/repc)]([http://pizzachili.dcc.uchile.cl/repc](http://pizzachili.dcc.uchile.cl/repc)) corpus.html), which is detailed in Table 1. As a comparison method, we used the online pattern matching for EDM called online ESP (baseline) [17] that approximates EDM between a query \(Q\) and substrings of the length of \(|Q|\) of each position of an input text. We randomly selected \(S[i,j]\) as the query pattern \(Q\) for each \(|Q|=50,100,500,1000\) and examined the performance. \begin{table}
\begin{tabular}{c c c c} \hline
**Dataset** & **Length** & \(|\Sigma|\) & **Size (MB)** \\ \hline einstein & \(467,626,544\) & \(139\) & \(446\) \\ cere & \(461,286,644\) & \(5\) & \(440\) \\ \hline \end{tabular}
\end{table} 
Table 1: Summary of datasets. Table 2 shows the memory consumption in the search of the siEDM and baseline. The memory consumption of siEDM was larger than the baseline for both texts because the baseline does not have characteristic vectors of each node and length vector. Table 3 shows the size for each component of the index structure and the time for building the index structure on einstein and cere datasets. Most of the size of the index structure was consumed by the characteristic vector \(F\). The index size of cere was much larger than that of einstein. The index sizes of cere and einstein were approximately 16 megabytes and 256 megabytes, respectively, because the number of variables generated from cere was much larger than that generated from einstein. The number of variables generated from einstein was \(305,098\) and the number of variables generated from cere was \(4,512,406\). The construction times of the index structures were \(118\) s for einstein and \(472\) s for cere. The results for constructing the index structures demonstrate the applicability of siEDM to moderately large, repetitive texts. Figure 5 shows the total search time (sec.) of siEDM and the baseline for einstein and cere in distance thresholds \(\tau\) from 10 to 60. In addition, this result does not contain the case \(\tau<10\) because siEDM found no candidate under the condition. The query length is one of \(\{50,100,500,1000\}\). Because the search time of baseline is linear in \(|S|+|Q|\), we show only the fastest case: \(q=|Q|=50\). The search time of siEDM was faster than baseline in most cases. Figure 6 shows the detailed search time in second. CF is the time for finding candidates of \(Q\) in \(T(S)\), DIST is the time for computing approximated \(L_{1}\) distance by characteristic vectors, and PC is the time for determining the positions of all \(|Q|\)-grams within the threshold \(\tau\). Figure 6: Details of search time for different \(|Q|\) and \(\tau\): time for candidate findings, CF, time for \(L_{1}\)-distance computations, DIST, and time for position computations, PC. (**a**) and (**b**) correspond to CF, (**c**) and (**d**) correspond to DIST, and (**e**) and (**f**) correspond to PC of einstein and cere, respectively. Figure 7 shows the number of nodes \(T(S)\) visited by the algorithm, #TN, the number of candidate \(|Q|\)-grams computed by _FindCandidates_, #CAND, the number of true positives among candidate \(|Q|\)-grams, #TP, and the number of occurrences, #OCC. The most time-consuming task is the candidate finding. By the monotonicity of characteristic vectors, pruning the search space for small distance thresholds and long query length is more efficient.