# A DFT-Based Running Time Prediction Algorithm for Web Queries
## 5 Experimental Evaluation  
### Data Collection and Methodology  
The research was conducted using a query log and two document collections of different sizes. We build an inverted index for each one of these collections by using the Terrier IR platform ([[http://terrier.org/](http://terrier.org/)]([http://terrier.org/](http://terrier.org/)), accessed on 19 June 2021). We pruned the index to keep only the data related to the terms of the query log. Once the indexes were built, we processed the query log using these indexes to retrieve the most relevant document results for each query. In this section, we will further describe the query log, the document collection, the hardware, deployment details and the baseline algorithm used to compare the results obtained by our DFT-based query time prediction algorithm. In the following sections, we first evaluate the accuracy of the prediction algorithm with different machine learning methods. We show that the best accuracy is obtained with a feed-forward neural network with back-propagation using five neurons in the hidden layer. Then, we present the accuracy and the performance evaluation for our proposal and the baseline algorithm. Finally, we show the benefits of our proposal to facilitate the assignment of threads to incoming queries. **Query log:** We use a query log containing 20,000 queries in English selected from the TrecMillion Query Track ([[https://trec.nist.gov/data/million.query09.html](https://trec.nist.gov/data/million.query09.html)]([https://trec.nist.gov/data/million.query09.html](https://trec.nist.gov/data/million.query09.html)), accessed on 19 June 2021). The query log is a list of text query like \"used car parts\", \"poker tournaments\" and \"lake links\". From this dataset we selected unique queries with two or more terms and removed the stopwords (e.g., this, that, these, etc.). The resulting query log has 15,000 queries. **ClueWeb09 Dataset:** We use a 50.2 million document collection from the TREC ClueWeb09 dataset (category B) ([[http://www.lemurproject.org/clueweb09.php/](http://www.lemurproject.org/clueweb09.php/)]([http://www.lemurproject.org/clueweb09.php/](http://www.lemurproject.org/clueweb09.php/)), accessed on 19 June 2021). This collection has a total of 428,136,613 unique documents. The resulting index size for this collection is 60.2 GB with 10,230 different terms. **Gov2 Dataset:** We use a second collection named TREC Gov2 with 25.2 million documents crawled from.gov sites ([[http://ir.dcs.gla.ac.uk/test_collections/gov2-summary.htm](http://ir.dcs.gla.ac.uk/test_collections/gov2-summary.htm)]([http://ir.dcs.gla.ac.uk/test_collections/gov2-summary.htm](http://ir.dcs.gla.ac.uk/test_collections/gov2-summary.htm)), accessed on 19 June 2021). It includes html and text, plus the extracted text of pdf, word and postscript. The resulting index size is 13.7 GB with 12,062 different terms. **Hardware and Deployment Details:** The running time of each query includes the preprocessing of uppers bounds plus the time required by the WAND or the BM-WAND iterators to process the query. The running times for the actual execution of the query processing strategies were obtained on an Intel Processor Core i7-3820 with 4 Cores (8 threads) and 32 GB RAM. All the experiments were performed with the whole inverted index loaded into main memory. In the case of the ClueWeb09, due to the index size is larger than the size of the main memory of the hardware, we performed the experiments with batches of 500 queries each. Only the posting lists associated with the terms present in each batch are loaded into the main memory using on average 22 GB of memory space. The average execution time of each query is measured independently one by one.