# 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
\begin{table}
\begin{tabular}{l c c c c c c c c c c} \hline \hline  & \multicolumn{8}{c}{**Neurons in the Hidden Layer**} \\ \cline{2-10}  & \multicolumn{2}{c}{**1**} & \multicolumn{2}{c}{**5**} & \multicolumn{2}{c}{**10**} & \multicolumn{2}{c}{**25**} & \multicolumn{2}{c}{**50**} \\
**PrC** & \multicolumn{2}{c}{**RMSE**} & \multicolumn{2}{c}{**PrC**} & \multicolumn{2}{c}{**RMSE**} & \multicolumn{2}{c}{**PrC**} & \multicolumn{2}{c}{**RMSE**} & \multicolumn{2}{c}{**PrC**} & \multicolumn{2}{c}{**RMSE**} \\ \hline \multicolumn{10}{c}{**LBM-WAND (L)/SBM-WAND (S)**} \\ \hline \multicolumn{10}{c}{**1 thread**} \\ \hline Baseline-L/S & **0.898** & **0.049** & 0.923 & 0.043 & 0.908 & 0.047 & 0.862 & 0.059 & 0.844 & 0.063 \\ DFT-based-L/S & 0.886 & 0.052 & **0.930** & *** 0.041** & **0.928** & **0.042** & **0.925** & **0.043** & **0.919** & **0.044** \\ \hline \multicolumn{10}{c}{**2 threads**} \\ \hline Baseline-L & **0.912** & **0.047** & 0.932 & 0.042 & 0.925 & 0.044 & 0.894 & 0.052 & 0.876 & 0.058 \\ DFT-based-L & 0.896 & 0.051 & **0.944** & *** 0.038** & **0.940** & **0.039** & **0.941** & **0.039** & **0.918** & **0.046** \\ \hline Baseline-S & **0.897** & **0.051** & 0.901 & 0.050 & 0.891 & 0.054 & 0.861 & 0.062 & 0.813 & 0.074 \\ DFT-based-S & 0.880 & 0.055 & **0.926** & *** 0.043** & **0.929** & **0.043** & **0.906** & **0.049** & **0.903** & **0.050** \\ \hline \multicolumn{10}{c}{**4 threads**} \\ \hline Baseline-L & **0.920** & **0.044** & 0.945 & 0.037 & 0.928 & 0.043 & 0.921 & 0.045 & 0.884 & 0.055 \\ DFT-based-L & 0.902 & 0.048 & **0.948** & **0.035** & **0.951** & *** 0.034** & **0.949** & **0.035** & **0.928** & **0.042** \\ \hline Baseline-S & **0.897** & **0.052** & 0.905 & 0.050 & 0.901 & 0.051 & 0.865 & 0.061 & 0.853 & 0.064 \\ DFT-based-S & 0.875 & 0.056 & **0.926** & *** 0.044** & **0.927** & **0.044** & **0.925** & **0.044** & **0.918** & **0.047** \\ \hline \multicolumn{10}{c}{**8 threads**} \\ \hline Baseline-L & **0.939** & **0.035** & 0.955 & 0.031 & 0.954 & 0.031 & 0.948 & 0.034 & 0.922 & 0.042 \\ DFT-based-L & 0.927 & 0.039 & **0.956** & **0.030** & **0.963** & **0.028** & **0.967** & *** 0.026** & **0.954** & **0.031** \\ \hline Baseline-S & **0.913** & **0.050** & 0.936 & 0.043 & 0.927 & 0.046 & 0.902 & 0.053 & 0.891 & 0.057 \\ DFT-based-S & 0.892 & 0.055 & **0.938** & *** 0.042** & **0.938** & **0.042** & **0.925** & **0.047** & **0.919** & **0.048** \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Prediction ability of the baseline and proposed algorithms for query running time prediction under two multi-threaded query processing strategies for different number of threads. For each case the best value for Pearson Correlation (PrC) and error RMSE are indicated in boldface type. The smallest RMSE values are indicated with *. The correlation and error values are obtained by comparing against the actual implementation of each multi-threaded query processing strategy: LBM-WAND (L) and SBM-WAND (S) both executed under ClueWeb09-BM25.