# A DFT-Based Running Time Prediction Algorithm for Web Queries
## 4 A DFT-Based Query Running Time Prediction Algorithm
### Term Coefficients  
Given a query \(q\) containing the terms \(t_{l}\) with \(l\geq 1\), where each term has a posting list \(L_{t}\) containing pairs \(<d,w(d,t)>\) where \(d\) is the document identifier and \(w(d,t)\) is the score of the term in the document (e.g., the frequency of occurrence of the term \(t\) in the document \(d\)), our DFT-based algorithm works as follows. We use information regarding the frequency spectrum of density functions \(\Phi_{t}\) obtained from the posting lists of the terms \(t_{l}\in q\), and the information related to the spectrum of frequency of the processing time \(T(t_{l},k)\) for each term \(t_{l}\) required to retrieve the top-\(k\) document results. The spectrum of frequencies is obtained with the discrete Fourier transform (DFT). In addition, we use: (a) the size of each posting list \(s_{t}=|L_{t}|\) (i.e., the number of documents where the term appears), (b) the processing time for \(T(t,10)\), \(T(t,100)\), \(T(t,1000)\) and for \(T\) (\(t\), 10,000), and (c) the threshold value for the top-\(k\) document. Then, we describe each term with a five dimension vector \(\psi:<\psi_{0},\psi_{1},\psi_{2},\psi_{3},\psi_{4}>\). The density function \(X_{DFT}\) of the posting lists of the term \(t_{l}\), describes the search space \(\Omega_{t}\) of the posting list \(L_{t}\). The \(X_{DFT}\) of the processing time functions \(T(t,k)\) describes the differences of the times required to process the posting list of a term \(t\) with different \(k\) values. In practice, the values of \(X_{DFT}[u]\) are the \(u\)-th coefficients of Fourier and express the frequency content of a function or a signal. In this analysis, the DFT of \(\Phi_{t}\) can be considered as a characterization of the distribution of the values \(w(d,t)\) and, therefore, it can be seen as a function of bulk density in the frequency domain. We use the spectral power density of \(X_{DFT}\) over \(w(d,t)\), because it represents the cost of processing the signal in the frequency domain. It shows how the power is scattered as a function of the frequency \(F=1/10\), which is the minimum frequency (or fundamental frequency) of the DFT. The fundamental frequency \(F=1/10\) describes the density of posting lists by using the convolution of the broader sinusoidal signal. Thus, it allows us to describe well the posting lists that have a higher density. We also use the magnitude of the spectrum of the fundamental frequency \(F=1/4\) of the \(DFT\) for the posting lists and for the processing times obtained for each term \(T(t,k)\), which describes the difference between the processing times as the value of \(k\) increases in a quadratic way. Table 2 summarizes the descriptors used in the proposed prediction algorithm. **PSD of \(\Phi_{t}\) at a frequency \(1/10\): \(\psi_{0}\)** is the Power Spectral Density (PSD) of the DFT of \(\Phi_{t}\) in the fundamental frequency \(F=1/10\). The calculation is \(|X_{DFT}[u]\{\Phi_{t}\}|^{2},u=1\). \(\Phi_{t}\) (Equation (1)) is a vector containing the cumulative sums of \(\Phi_{G}\) (Equation (2)) of scores \(w(d,t)\) of each document \(d\in L_{t}\) inside the intervals \(l_{j}\). Each j-th interval \(I\) is equi-spaced at the rate of \(\#Postings/10\) items. If there are empty intervals, the cumulative sum is zero in those positions. Each value of \(\Phi_{t,i}\) is obtained with Equation (3). \[\Phi_{t}=<\Phi_{t,1},\Phi_{t,2},\ldots,\Phi_{t,i},\ldots\Phi_{t,10}> \tag{1}\]  
\[\Phi_{G}=max\{\sum_{d\in L_{t}}w(d,t)\},t\in Inverted\;\;Index \tag{2}\]  
\[\Phi_{t,i}=\frac{1}{\Phi_{G}}\sum_{d\in l_{i}}w(d,t) \tag{3}\]  
We set the number of intervals \(I=10\) because a greater number of intervals implies a distribution of the average power of the signal in a greater number of frequencies of the DFT. In other words, by increasing the number of intervals the percentage of documents that quantify the density of \(w(d,t)\) decreases inside each interval.