Istituto di Scienza e Tecnologie dell'Informazione     
Macdonald C., Tonellotto N., Ounis I. Learning to predict response times for online query scheduling. In: SIGIR 2012 - 35th International ACM SIGIR Conference on Research and Development in Information Retrieval (Portland, OR, USA, 12-16 August 2012). Proceedings, pp. 621 - 630. ACM, 2012.
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.
URL: http://dl.acm.org/citation.cfm?id=2348367&CFID=179990712&CFTOKEN=56023105
DOI: 10.1145/2348283.2348367
Subject Performance
H.3.3 Information Search & Retrieval

Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional