Fast ranking with additive ensembles of oblivious and non-oblivious regression trees
Journal paper accepted at ACM Transactions on Information Systems .
Abstract. Learning-to-Rank models based on additive ensembles of regression trees have been proven to be very eﬀective for scoring query results returned by large-scale Web search engines. Unfortunately, the computational cost of scoring thousands of candidate documents by traversing large ensembles of trees is high. Thus, several works have investigated solutions aimed at improving the eﬃciency of document scoring by exploiting advanced features of modern CPUs and memory hierarchies. In this paper, we present QuickScorer, a new algorithm that adopts a novel cache-eﬃcient representation of a given tree ensemble, it performs an interleaved traversal by means of fast bitwise operations, and also supports ensembles of oblivious trees. An extensive and detailed test assessment is conducted on two standard Learning-to-Rank datasets and on a novel very-large dataset we made publicly available for conducting signiﬁcant eﬃciency tests. The experiments show unprecedented speedups over the best state-of-the-art baselines ranging from 1.9x to 6.6x. The analysis of low-level proﬁling traces shows that QuickScorer eﬃciency is due to its cache-aware approach both in terms of data layout and access patterns, and to a control ﬂow that entails very low branch mis-prediction rates.