# A DFT-Based Running Time Prediction Algorithm for Web Queries
## 5 Experimental Evaluation
### An Application Case for Query Running Time Prediction
#### 5.5.1 Accuracy Evaluation of the DFT-Based Algorithm under Multi-Thread Query Processing  
We evaluate the predictive ability of the algorithm to determine the query running time for a given number of threads. This prediction is challenging since the running time does not decrease linearly with the number of threads. Table 8 shows the Pearson correlation (PrC) and the error RMSE obtained by both prediction algorithms for different number of neurons in the hidden layer and different number of threads (1, 2, 4 and 8). The correlation and error are evaluated against the actual execution of each multi-threading strategy (LBM-WAND and SBM-WAND). As we increase the number of threads, both prediction algorithms achieve a more accurate prediction of the query running time. This is mainly because the differences between the maximum and minimum query running times tend to be smaller with thread increase. The baseline prediction algorithm presents better prediction accuracy than our DFT-based algorithm for the case of a single neuron in the hidden layer. The results show that the proposed algorithm achieves more accurate predictions than the baseline algorithm with five and more neurons in the hidden layer. The SBM-WAND strategy presents relatively larger error values (RMSE) because in this case it is more difficult for the algorithm to predict the number of locks executed to control the accesses to the shared heap. Table 9 shows the query running times for 1, 2, 4 and 8 threads obtained with (i) the actual execution of the LBM-WAND (L) and SBM-WAND (S) strategies, (ii) the respective query running times predicted by the proposed algorithm and (iii) the respective query running times predicted by the baseline algorithm, both using 5 neurons in the hidden layer. The results show that the proposed algorithm reduces the absolute error (AAE) by 7% on average whereas the maximum absolute error (\(max_{e}\)) is reduced by 26% on average. For the single query demanding the maximum running time (\(max_{t}\)) the baseline algorithm underestimates its value by 16% on average, whereas the proposed algorithm is less effective in this case as it underestimates its value by 28% on average. Notice that the results in Table 9 show that the LBM-WAND strategy is 29% less efficient than the SBM-WAND strategy on average. This is true for the average values taken by considering the whole set of queries used in the experiments. However, for the same test dataset, LBM-WAND is on average 10% more efficient than SBM-WAND for a small subset of queries (5%). In practice, the size of this subset depends on the specific query contents and how frequently they occur in the dynamic incoming stream of user queries. Figure 5: At left side is the LBM-WAND strategy. At right side is the SBM-WAND strategy where all threads share a global heap. Finally, we show in Figure 6 the Pearson correlation reported by the baseline and the DFT-based algorithm with different values for top-\(k\) document results and different number of threads. The \(y\)-axis (left) shows the number of threads ranging from 1 to 8. The \(y\)-axis (right) shows the Pearson correlation from 80% to 100%. The \(x\)-axis shows the \(k\) values from 10 to 10,000. We show results obtained with the LMB-WAND strategy. Similar results were obtained for the SBM-WAND strategy. For \(k=10\), both prediction algorithms report similar results. With a larger \(k\) value, the DFT-based algorithm reports better results.