# A DFT-Based Running Time Prediction Algorithm for Web Queries
## 4 A DFT-Based Query Running Time Prediction Algorithm  
Query running time prediction has practical applications in the efficient assignment of resources. In particular, in this paper, we show its benefits for an efficient assignment of threads to incoming queries. The DFT-based algorithm can be used by a scheduler to decide for each query at runtime, whether to assign to it a single thread or more than one thread to process it depending on the estimated time. Furthermore, the scheduler can determine the number of threads to allocate to each query using the predictions provided by our algorithm. An efficient allocation of threads allows to obtain a better utilization of the resources and reduces the latencies of query execution times [10]. The algorithm proposed in this work uses a new approach to describe user queries with low-dimensional vectors. Our approach allows us to drastically reduce the computational cost without compromising the accuracy of the top-\(k\) document results. The cost of predicting a query running time is directly proportional to the number of inputs to the prediction algorithm, regardless of the particular document ranking algorithm being used. Any regression model with several independent variables \(x_{i}\) with an output dependent variable \(y\), must process the entire input vector \(x=\{x_{1},x_{2},\ldots,x_{p}\}\) of \(p\) descriptors. In particular, a basic regression model of several variables can be defined as \(y=\beta_{0}+\sum_{i=1}^{p}\beta_{i}x_{i}+\varepsilon\), which corresponds to a multiple linear regression model where \(\beta_{i}\) is the correlation coefficient to be obtained, \(\beta_{0}\) is the slope of the regression line and \(\varepsilon\) is the error. To predict the query running time, we propose to use the Discrete Fourier Transform (DFT). The DFT is an approximation of the Fourier Transform and is used to find the content in the frequency of signals that are periodic and discrete, which implies that in the domain of frequency they will also be periodic and discrete. The DFT includes in its descriptor signal data such as the variance, the arithmetic means, and factors associated with the continuity of the signal and its density. The signal obtained with the DFT satisfies the symmetry property [40]. Therefore, it allows us to use only half the components of the vector. These properties allow us to obtain a good characterization of the posting, since it includes in its signal (output of the DFT) descriptive information of an input signal. Thus, using the DFT allows to reduce the number of descriptors used to represent the information while remaining representative for each posting list. In particular, we use the DFT to:  
* Describe the distribution of scores of each document in the posting list of the terms and to determine how is the distribution of the scores of the documents with higher probability of being part of the top-\(k\)- document results. In this way, we describe the search space of each posting list. * Describe the variation of the running time of different queries as we retrieve a larger number of top-\(k\) document results. In this work, the distribution of the weights \(w(d,t)\) of the posting lists are treated as signals of the DFT, where these signals are the function of independent variables given by the random distribution of \(w(d,t)\) and determined by the order of the documents identifiers (docIDs). Low DFT frequencies are used to describe how the high values of \(w(d,t)\) are distributed (because they appear less frequently in the posting list according to the Zipf law [8]) and high DFT frequencies are used to describe the distribution of low values of \(w(d,t)\) (because they appear more frequently in the posting lists). Our DFT-based algorithm builds a query-vector in two stages as illustrated in Figure 4. During the off-line stage (Figure 4 on top), our proposal builds a five-dimensional term-vector to represent the posting lists of the terms stored in the inverted index.