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. QS (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 2x to 6.5x over state-of-the-art competitors. The paper proposing qs was awarded best paper at last ACM SIGIR conference.