Fast Ranking with Additive Ensembles of Oblivious and Non-Oblivious Regression Trees
Fast Ranking with Additive Ensembles of Oblivious and Non-Oblivious Regression Trees
复制标题
使用遗忘和非遗忘回归树的可加集成进行快速排序
DOI：
10.1145/2987380
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Rossano Venturini
中科院分区：
文献类型：
--
作者：
Domenico Dato;C. Lucchese;F. M. Nardini;S. Orlando;R. Perego;N. Tonellotto;Rossano Venturini
基于回归树的加性集成的学习排名模型已被证明对于对大型网络搜索引擎返回的查询结果进行评分非常有效。不幸的是，通过遍历大型树集合来对数千个候选文档进行评分的计算成本很高。因此，一些工作研究了旨在通过利用现代 CPU 和内存层次结构的高级功能来提高文档评分效率的解决方案。在本文中，我们提出了 QuickScorer，这是一种新算法，它采用给定树集成的新颖的高速缓存有效表示，通过快速按位运算执行交错遍历，并支持不经意树的集成。对两个标准的学习排名数据集和我们公开提供的用于进行显着效率测试的新颖的超大型数据集进行了广泛而详细的测试评估。实验显示，与最先进的基线相比，速度有了前所未有的提升，范围从 1.9 × 到 6.6 × 。低级分析跟踪的分析表明，QuickScorer 的效率归因于其在数据布局和访问模式方面的缓存感知方法，以及需要非常低的分支误预测率的控制流。
Learning-to-Rank models based on additive ensembles of regression trees have been proven to be very effective 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 efficiency of document scoring by exploiting advanced features of modern CPUs and memory hierarchies. In this article, we present QuickScorer, a new algorithm that adopts a novel cache-efficient representation of a given tree ensemble, performs an interleaved traversal by means of fast bitwise operations, and 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 significant efficiency tests. The experiments show unprecedented speedups over the best state-of-the-art baselines ranging from 1.9 × to 6.6 × . The analysis of low-level profiling traces shows that QuickScorer efficiency is due to its cache-aware approach in terms of both data layout and access patterns and to a control flow that entails very low branch mis-prediction rates.