# A DFT-Based Running Time Prediction Algorithm for Web Queries
## 2 Background
### Web Search Engines  
Web Search Engines (WSEs) are usually built as a collection of services hosted in large clusters of multi-core processors wherein each service is deployed on a set of processors supporting multi-threading. Typically, a WSE is composed of three services: the Front-Service (FS), the Cache-Service (CS) and the Index-Service (IS) [12; 13]. These services are deployed on clusters of multi-core processors and connected by high-speed communication networks [14; 15; 16]. They are organized on arrays of \(P\times R\) multi-core processors, where \(P\) is the level of data partitioning and \(R\) is the level of data replication.  
In Figure 1a, we show the query flow through the three services of a WSE. After a query arrives to an FS, it routes the query to the CS to determine if the query has been previously processed (step 2). The CS partition is selected by applying a hash function on the query terms. The replica is selected in a round-robin way. If the query is found in the cache memory (step 3), the CS sends the top-\(k\) document results identifiers (docIDs) to the FS, which builds the HTML page. Otherwise, if the query is not found in cache, the CS sends a miss message to the FS (also step 3). In this last case, the FS sends an index search request to a single replica of all \(P\) partitions of the index service (step 4). The replicas are selected in a round-robin way for each query. Then, each index service executes a ranking algorithm to compute the top-\(k\) document results and sends them to the FS (step 5). Finally, the FS merges the partial results, builds the web page for the user (step 7) and sends an update message to the CS (step 6).  
The computation of the top-\(k\) documents results for user queries is a high-computational demanding operation executed by the IS. A ranking algorithm is executed on an inverted index or inverted file [8]. The index is built from a large set of web documents. The index is composed of a vocabulary table (which contains the \(C\) distinct relevant terms found in the  
\begin{table}
\begin{tabular}{c c} \hline
**Tech./Acronym** & **Description** \\ \hline BM25 & Ranking function to estimate the relevance of documents. \\ BM-WAND & Block-Max WAND. Optimized pruning technique that discard \\  & not relevant documents for a query. \\  & It uses compressed data organized in blocks. \\ \hline ClueWeb09 & Collection of 428,136,613 unique documents. \\ \hline CS & Cache-Service. It is a service component of a WSE. \\ \hline DFT & Discrete Fourier Transform \\ \hline FS & Front-Service. It is a service component of a WSE. \\ \hline Gov2 & Collection of 25.2 million documents. \\ \hline IS & Index Service. It is a service component of a WSE. \\ \hline LBM-WAND & Local BM-WAND multi-thread strategy. \\ \hline PSD & Power Spectral Density \\ \hline SBM-WAND & Shared BM-WAND multi-thread strategy. \\ \hline TF-idf & Ranking function to estimate the relevance of documents. \\ \hline top-\(k\) & Best document results for a query \\ \hline WAND & Weighted AND. Pruning technique used to discard \\  & not relevant documents for a query. \\ \hline WSE & Web Search Engine \\ \hline \end{tabular}
\end{table}
Table 1: Description of the technical words.  
document collection) and a set of posting lists. For each term \(c\), there is a list of data items (called postings) storing the identifiers of the documents that contain the term \(c\), along with additional data used for ranking purposes. Figure 1b shows the main steps executed inside an IS processor to process an user query [15]. First, a local top-\(k\) cache is used to search for pre-computed queries inside each IS processor. Then, an intersection cache--which keeps the documents belonging to the intersection of posting lists of previously processed query terms--and the inverted index are used to quickly determine the list of documents that contain the query terms. Finally, the IS computes the ranking of the resulting set of documents.