Document - Learning to predict response times for online query scheduling

2012

Conference article Open Access

Learning to predict response times for online query scheduling

Macdonald C., Tonellotto N., Ounis I.

Experimentation Performance H.3.3 Information Search & Retrieval

Dynamic pruning strategies permit efficient retrieval by not fully scoring all postings of the documents matching a query - without degrading the retrieval effectiveness of the topranked results. However, the amount of pruning achievable for a query can vary, resulting in queries taking different amounts of time to execute. Knowing in advance the execution time of queries would permit the exploitation of online algorithms to schedule queries across replicated servers in order to minimise the average query waiting and completion times. In this work, we investigate the impact of dynamic pruning strategies on query response times, and propose a framework for predicting the efficiency of a query. Within this framework, we analyse the accuracy of several query efficiency predictors across 10,000 queries submitted to in-memory inverted indices of a 50-million-document Web crawl. Our results show that combining multiple efficiency predictors with regression can accurately predict the response time of a query before it is executed. Moreover, using the efficiency predictors to facilitate online scheduling algorithms can result in a 22% reduction in the mean waiting time experienced by queries before execution, and a 7% reduction in the mean completion time experienced by users.

Source: 35th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 621–630, Portland, OR, USA, 12-16 August 2012

Publisher: ACM Press, New York, USA

Metrics

Back to previous page

Cite as

BibTeX entry

@inproceedings{oai:it.cnr:prodotti:218941,
	title = {Learning to predict response times for online query scheduling},
	author = {Macdonald C. and Tonellotto N. and Ounis I.},
	publisher = {ACM Press, New York, USA},
	doi = {10.1145/2348283.2348367},
	booktitle = {35th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 621–630, Portland, OR, USA, 12-16 August 2012},
	year = {2012}
}