# A DFT-Based Running Time Prediction Algorithm for Web Queries
## 3 Related Work  
Query running time prediction is a challenging task widely used in database management systems [1; 2; 3; 4; 5; 6; 7]. In the context of Web search engines, query running time prediction deals with additional challenges such as dynamic pruning techniques. Dynamic pruning techniques such as the WAND or the BM-WAND can improve the efficiency of queries, but they can take different amounts of time for different queries. That is because their cost is not directly related to the posting list lengths of the query terms as many documents can be skipped. In this context and under different incoming user query rates, query running time prediction algorithms based on machine learning techniques can be useful to determine in advance which resources can be allocated to a given query. The work in [20] presented a query running time prediction algorithm that aggregates the terms features into statistics related to the query. The results of the aggregations are used as input to a learned regression model. This work showed promising initial results for disk-based indices. Later, the work in [21] applied the prediction algorithm presented in [20] for evenly distributing the query workload across processors acting as replicas for each partition of the document collection. The work in [22] presented an algorithm which is based on the relative entropy between a query language and the corresponding collection language model. The work in [10] specifically presented a query running time predictor for the WAND technique. The proposed predictor is designed for distributed search engines. The authors propose to use a vector with 42 descriptors to represent different features of the queries and the respective posting lists. To estimate the query running time, the proposed algorithm uses a linear regression method which has been trained from the statistics obtained by the aggregations of the terms features. The work in [23] improves the accuracy of [10] by including additional data on the query terms for the prediction of the running time. More recently, the authors in [24] proposed to use index synopses which are stochastic samples of the full index for attaining accurate timing predictions. The work in [25] proposed to model the complexity of query features by using a personalization method. This approach outperformed existing predictors in terms of accuracy and memory consumption. The query running time predictor was used to decide  
Figure 3: Running time of individual queries in milliseconds sorted from low to high values. (a) Results obtained with the WAND algorithm. (b) Results obtained with the BM-WAND algorithm. on whether to process a single query with multiple threads (the ones with predicted large running times) or a single thread (the ones with predicted small running times). The work in [26] determined the most relevant parameters used in [10] and based on that finding proposed to optimize memory usage on heterogeneous hardware. The authors proposed a predictor named Delayed, Dynamic, and Selective (DDS). First, queries are executed for a short period of time \(D\) so short-running queries can be completed without prediction overhead. Then, the algorithm collects 10 features of the query after running it during the first step. In the final step, the algorithm classifies the queries as long or medium using a threshold value. This work was extended in [27] by presenting more comprehensive experimental evaluation. The work in [28] aimed to achieve a minimum query response time when query traffic is high. The algorithm is configured to prune more or less aggressively, depending on the expected duration of the query. The value of \(k\) is also estimated in [29]. Nevertheless, in [29] the effectiveness of the search engine is not compromised as it ensures the retrieval of the actual top-k document results. The work in [30] presented a scheduler to process queries concurrently by using multi-threading. It also allows to execute updates in the posting lists.