Ranking documents efficiently with QuickScorer

This discussion paper presents our recent work on the efficiency of Learning-to-Rank models based on additive ensembles of regression trees. These models, although computationally expensive, have proven to provide a very effective solution to the problem of ranking query results returned by Web search engines, a scenario where quality and efficiency requirements are very demanding. QUICKSCORER (QS), our novel scoring algorithm, adopts a novel bitvector representation of the tree-based ranking model, and performs an interleaved traversal of the ensemble by means of simple logical bitwise operations. Due to its cache-aware approach, both in terms of data layout and access patterns, and to a control flow that entails very low branch mis-prediction rates, QS performance are impressive, resulting in speedups from 2.4x to 5.9x over the state-of-the-art competitor. The paper proposing QS was awarded best paper at last ACM SIGIR conference.