# A DFT-Based Running Time Prediction Algorithm for Web Queries
## 2 Background
### Challenges for Query Running Time Prediction  
In this section, we expose the difficulty in predicting query running time for the WAND and BM-WAND techniques. The datasets used in the following experiments are described below in Section 5. In particular, the ClueWeb09 and the Gov2 Web collections are considered standard collections for comparative performance evaluation.  
Figure 1: (**a**) Query processing in a WSE and (**b**) inside an index service processor.  
In Figure 2, we show running times in milliseconds achieved by both ranking algorithms with different values of \(k\) for the top-\(k\) documents using the ClueWeb09 collection. Over a large set of input queries, the results show that for each \(k\) the average running time values do not increase linearly with \(k\). As the value of \(k\) increases, both techniques present nearly logarithmic increasing running times. This is because the heap used to keep the current top-\(k\) documents is larger as more documents are kept inside the heap until the algorithm finishes query processing. The probability of finding a document more relevant than those currently stored in the heap is also higher so that more insertions and eliminations are performed on average. The results show that the BM-WAND algorithm presents lower running times than the WAND algorithm. In Figure 1(a), the WAND algorithm presents about twice the time reported by the BM-WAND algorithm for small values of \(k\). For large values of \(k\), the difference reported by both algorithms is 23% on average. However, the results in Figure 1(b), obtained with the Gov2 collection, show that the difference between both dynamic pruning techniques tends to be smaller.  
The challenge is to predict the behaviour of individual queries whilst performing thread management at run time. The results in Figure 2 show that this is at least dependent on the document collection and the combination of algorithms used to perform the document ranking process.  
In Figure 3, we show the running time in milliseconds required to process 15,000 queries from the query log, using the ClueWeb09 and the Gov2 Web collections. We also show results with the BM25 and TF-IDF document scoring algorithms. We set \(k=1000\). The \(x\)-axis represents the 15,000 queries sorted by their running time from low to high values. The \(y\)-axis shows the running time of the individual queries in log scale. In Figure 2(a), we show the results obtained with the WAND strategy. The BM25 scoring algorithm tends to present lower running times than the TF-IDF scoring algorithm. This is counter intuitive since BM25 demands more computations than TF-IDF per processed document. The reason for this behaviour is the effect that the calculated document score values have on the heap used to hold the current top-\(k\) documents. In Figure 2(b), we show results obtained with the BM-WAND algorithm. In this case, all curves tend to be almost overlapped. However, the query running times obtained with the ClueWeb09 collection and the BM25 document scoring algorithm tend to be slightly higher. As in practice the index service, at single processor level, must solve each query from the input stream in least than, say, 50 or 100 ms on commodity hardware, Figure 3 shows that it is relevant to reduce individual running times by means of multi-threading. In this case, the challenge is to determine at run time what strategy to apply to perform multi-threaded query processing.  
Figure 2: Average execution time in milliseconds (ms) reported by the WAND and the BM-WAND algorithms with the (**a**) ClueWeb09 and the (**b**) Gov2 Web collections.  
The results presented in this section show that the running times reported by the WAND and BM-WAND are highly influenced by a few parameters such as the number of document score evaluations, the specific query contents and the features of the document collection. The proposed prediction algorithm is designed to properly consider these parameters and their impact on the query running time.