# A DFT-Based Running Time Prediction Algorithm for Web Queries
## 5 Experimental Evaluation
### An Application Case for Query Running Time Prediction  
In this section, we describe two multi-threaded query processing strategies [29] as an application case for the query running time prediction algorithm presented in the paper. In the first strategy, called Local BM-WAND (LBM-WAND), each thread keeps a local heap to hold the top-\(k\) documents calculated by the thread. The posting lists of the documents index are distributed among a total of \(T\) threads using the rule \(\mathit{docID}\mod T\). This posting list partition rule ensures that any given document is always assigned to the same thread. Then, each thread processes the query using its own local inverted index. At the end of the query processing process, we merge the local heaps of each thread to select the top-\(k\) document results. To this end, a synchronization barrier is executed before the merge operation. The second strategy, called Shared BM-WAND(SBM-WAND), uses the same index partition scheme as the LBM-WAND but all threads update a single global heap of size \(k\) holding the top-\(k\) results. Therefore, the SBM-WAND strategy does not perform a merge of partial document results at the end of the process as it already contains the top-\(k\) results. A lock operation is executed to guarantee exclusive access to the shared heap during updates to prevent from read-write conflicts. Figure 5 describes these two parallel strategies for query processing.  
Experimentally, we have found [29] that the LBM-WAND strategy performs better than the SBM-WAND strategy when the sequential query running time is below a given \(\beta\) value. The SBM-WAND strategy outperforms the LBM-WAND strategy for queries demanding running times larger than \(\beta\). In practice, the value of \(\beta\) can be calculated as a part of the training process for the DFT algorithm. Thus, for each incoming query, a scheduler uses the proposed DFT-based algorithm to decide on which strategy to apply at run time.  
The number of threads \(T\) required for solving single queries is determined as the minimum necessary to ensure that no query is solved beyond an upper bound for the response time in the index service. In this way, the total number of threads available for query processing can be grouped into a set of \(T\)-threads units capable of using either LBM-WAND or SBM-WAND for solving single queries in parallel. In practice, for our Web collections and test processor, with \(T=8\) threads is sufficient for achieving query response times below 50 ms which is a standard upper bound for search engines.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & **Vector Construction Time** & \multicolumn{4}{c}{**Neuronal Network**} \\ \hline Algorithm & 2 terms & 5 terms & 5 neurons & 10 neurons & 25 neurons & 50 neurons \\ \hline Baseline & 22,129 ns & 31,429 ns & 6844 ns & 9150 ns & 14,108 ns & 23,397 ns \\ DFT-based & **2095 ns** & **2376 ns** & **4610 ns** & **5238 ns** & **6984 ns** & **8894 ns** \\ \hline \hline \end{tabular}
\end{table}
Table 6: Running time in nanoseconds reported by both the proposed algorithm and the baseline algorithm. The best results are highlighted in boldface type.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Term-Vector** & **Query-Vector** & **Total** \\ \hline Baseline & 92 Bytes & 213 Bytes & 305 Bytes \\ \hline DFT-based & 45 Bytes & 46 Bytes & 91 Bytes \\ \hline \hline \end{tabular}
\end{table}
Table 7: Memory consumption per query in bytes required to store the descriptors of the term-vectors and the query-vectors.