ML Anthology

QuickScorer: Efficient Traversal of Large Ensembles of Decision Trees

Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, Nicola Tonellotto, Rossano Venturini
ECML-PKDD 2017 pp. 383-387
doi:10.1007/978-3-319-71273-4_36 /ecmlpkdd/2017/lucchese2017ecmlpkdd-quickscorer/

Abstract

Machine-learnt models based on additive ensembles of binary regression trees are currently deemed the best solution to address complex classification, regression, and ranking tasks. Evaluating these models is a computationally demanding task as it needs to traverse thousands of trees with hundreds of nodes each. The cost of traversing such large forests of trees significantly impacts their application to big and stream input data, when the time budget available for each prediction is limited to guarantee a given processing throughput. Document ranking in Web search is a typical example of this challenging scenario, where the exploitation of tree-based models to score query-document pairs, and finally rank lists of documents for each incoming query, is the state-of-art method for ranking (a.k.a. Learning-to-Rank ). This paper presents QuickScorer , a novel algorithm for the traversal of huge decision trees ensembles that, thanks to a cache- and CPU-aware design, provides a ${\sim } 9 \! \times $ speedup over best competitors.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Lucchese et al. "QuickScorer: Efficient Traversal of Large Ensembles of Decision Trees." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2017. doi:10.1007/978-3-319-71273-4_36

Markdown

[Lucchese et al. "QuickScorer: Efficient Traversal of Large Ensembles of Decision Trees." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2017.](https://mlanthology.org/ecmlpkdd/2017/lucchese2017ecmlpkdd-quickscorer/) doi:10.1007/978-3-319-71273-4_36

BibTeX

@inproceedings{lucchese2017ecmlpkdd-quickscorer,
  title     = {{QuickScorer: Efficient Traversal of Large Ensembles of Decision Trees}},
  author    = {Lucchese, Claudio and Nardini, Franco Maria and Orlando, Salvatore and Perego, Raffaele and Tonellotto, Nicola and Venturini, Rossano},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2017},
  pages     = {383-387},
  doi       = {10.1007/978-3-319-71273-4_36},
  url       = {https://mlanthology.org/ecmlpkdd/2017/lucchese2017ecmlpkdd-quickscorer/}
}