A DFT-Based Running Time Prediction Algorithm for Web Queries

Oscar Rojas, Veronica Gil-Costa and Mauricio Marin
Additional contact information
Oscar Rojas: CITIAPS, Universidad de Santiago, Santiago 9170020, Chile
Veronica Gil-Costa: CONICET, Universidad Nacional de San Luis, San Luis 5700, Argentina
Mauricio Marin: CITIAPS, Universidad de Santiago, Santiago 9170020, Chile

Future Internet, 2021, vol. 13, issue 8, 1-21

Abstract: Web search engines are built from components capable of processing large amounts of user queries per second in a distributed way. Among them, the index service computes the top- k documents that best match each incoming query by means of a document ranking operation. To achieve high performance, dynamic pruning techniques such as the WAND and BM-WAND algorithms are used to avoid fully processing all of the documents related to a query during the ranking operation. Additionally, the index service distributes the ranking operations among clusters of processors wherein in each processor multi-threading is applied to speed up query solution. In this scenario, a query running time prediction algorithm has practical applications in the efficient assignment of processors and threads to incoming queries. We propose a prediction algorithm for the WAND and BM-WAND algorithms. We experimentally show that our proposal is able to achieve accurate prediction results while significantly reducing execution time and memory consumption as compared against an alternative prediction algorithm. Our proposal applies the discrete Fourier transform (DFT) to represent key features affecting query running time whereas the resulting vectors are used to train a feed-forward neural network with back-propagation.

Keywords: distributed query ranking algorithm; discrete Fourier transform; query scheduling for multi-core processors (search for similar items in EconPapers)
JEL-codes: O3 (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/1999-5903/13/8/204/pdf (application/pdf)
https://www.mdpi.com/1999-5903/13/8/204/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jftint:v:13:y:2021:i:8:p:204-:d:607882

Access Statistics for this article

Future Internet is currently edited by Ms. Grace You

More articles in Future Internet from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().