Efficient & Effective Selective Query Rewriting with Efficiency Predictions

To enhance effectiveness, a user’s query can be rewritten internally by the search engine in many ways, for example by applying prox- imity, or by expanding the query with related terms. However, ap- proaches that benefit effectiveness often have a negative impact on efficiency, which has impacts upon the user satisfaction, if the query is excessively slow. In this paper, we propose a novel framework for using the predicted execution time of various query rewritings to select between alternatives on a per-query basis, in a manner that ensures both effectiveness and efficiency. In particular, we propose the prediction of the execution time of ephemeral (e.g., proximity) posting lists generated from uni-gram inverted index posting lists, which are used in establishing the permissible query rewriting alter- natives that may execute in the allowed time. Experiments examin- ing both the effectiveness and efficiency of the proposed approach demonstrate that a 49% decrease in mean response time (and 62% decrease in 95th-percentile response time) can be attained without significantly hindering the effectiveness of the search engine.