{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T05:16:21Z","timestamp":1784178981796,"version":"3.55.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,12,12]],"date-time":"2016-12-12T00:00:00Z","timestamp":1481500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>\n            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 Q\n            <jats:sc>uick<\/jats:sc>\n            S\n            <jats:sc>corer<\/jats:sc>\n            , 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 \u00d7 to 6.6 \u00d7 . The analysis of low-level profiling traces shows that Q\n            <jats:sc>uick<\/jats:sc>\n            S\n            <jats:sc>corer<\/jats:sc>\n            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.\n          <\/jats:p>","DOI":"10.1145\/2987380","type":"journal-article","created":{"date-parts":[[2016,12,13]],"date-time":"2016-12-13T14:34:05Z","timestamp":1481639645000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":64,"title":["Fast Ranking with Additive Ensembles of Oblivious and Non-Oblivious Regression Trees"],"prefix":"10.1145","volume":"35","author":[{"given":"Domenico","family":"Dato","sequence":"first","affiliation":[{"name":"Tiscali Italia S.p.A., Cagliari, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claudio","family":"Lucchese","sequence":"additional","affiliation":[{"name":"ISTI--CNR, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franco Maria","family":"Nardini","sequence":"additional","affiliation":[{"name":"ISTI--CNR, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Salvatore","family":"Orlando","sequence":"additional","affiliation":[{"name":"Ca\u2019 Foscari University of Venice, Venezia Mestre, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raffaele","family":"Perego","sequence":"additional","affiliation":[{"name":"ISTI--CNR, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicola","family":"Tonellotto","sequence":"additional","affiliation":[{"name":"ISTI--CNR, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rossano","family":"Venturini","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.73"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36973-5_13"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718538"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 6th Italian Information Retrieval Workshop (IIR).","author":"Capannini Gabriele","year":"2015","unstructured":"Gabriele Capannini , Domenico Dato , Claudio Lucchese , Monica Mori , Franco Maria Nardini , Salvatore Orlando , Raffaele Perego , and Nicola Tonellotto . 2015 . QuickRank: A C++ suite of learning to rank algorithms . In Proceedings of the 6th Italian Information Retrieval Workshop (IIR). Gabriele Capannini, Domenico Dato, Claudio Lucchese, Monica Mori, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, and Nicola Tonellotto. 2015. QuickRank: A C++ suite of learning to rank algorithms. In Proceedings of the 6th Italian Information Retrieval Workshop (IIR)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2016.05.004"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939785"},{"key":"e_1_2_1_8_1","volume-title":"Salvatore Orlando, Raffaele Perego, Nicola Tonellotto, and Rossano Venturini.","author":"Dato Domenico","year":"2015","unstructured":"Domenico Dato , Claudio Lucchese , Franco Maria Nardini , Salvatore Orlando, Raffaele Perego, Nicola Tonellotto, and Rossano Venturini. 2015 . A method to rank documents by a computer, using additive ensembles of regression trees and cache optimization, and search engine using such a method. Tiscali S.p.A. PCT 29914, (pending) (2015). Domenico Dato, Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, Nicola Tonellotto, and Rossano Venturini. 2015. A method to rank documents by a computer, using additive ensembles of regression trees and cache optimization, and search engine using such a method. Tiscali S.p.A. PCT29914, (pending) (2015)."},{"key":"e_1_2_1_9_1","unstructured":"Jerome H. Friedman. 2001. Greedy function approximation: A gradient boosting machine. Ann. Stat. (2001) 1189--1232.  Jerome H. Friedman. 2001. Greedy function approximation: A gradient boosting machine. Ann. Stat. (2001) 1189--1232."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009932"},{"key":"e_1_2_1_11_1","volume-title":"Workshop and Conference Proceedings, JMLR. 63--76","author":"Gulin Andrey","year":"2011","unstructured":"Andrey Gulin , Igor Kuralenok , and Dmitry Pavlov . 2011 . Winning the transfer learning track of Yahoo&excl;\u2019s learning to rank challenge with yetirank . In Workshop and Conference Proceedings, JMLR. 63--76 . Andrey Gulin, Igor Kuralenok, and Dmitry Pavlov. 2011. Winning the transfer learning track of Yahoo&excl;\u2019s learning to rank challenge with yetirank. In Workshop and Conference Proceedings, JMLR. 63--76."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/582415.582418"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2911451.2911520"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 12th National Conference on Artificial Intelligence (AAAI). AAAI Press, 613--618","author":"Kohavi Ron","year":"1994","unstructured":"Ron Kohavi . 1994 . Bottom-up induction of oblivious read-once decision graphs: Strengths and limitations . In Proceedings of the 12th National Conference on Artificial Intelligence (AAAI). AAAI Press, 613--618 . Ron Kohavi. 1994. Bottom-up induction of oblivious read-once decision graphs: Strengths and limitations. In Proceedings of the 12th National Conference on Artificial Intelligence (AAAI). AAAI Press, 613--618."},{"key":"e_1_2_1_15_1","volume-title":"Working Notes of the AAAI-94 Workshop on Case-Based Reasoning. AAAI Press, 113--117","author":"Langley Pat","year":"1994","unstructured":"Pat Langley and Stephanie Sage . 1994 . Oblivious decision trees and abstract cases . In Working Notes of the AAAI-94 Workshop on Case-Based Reasoning. AAAI Press, 113--117 . Pat Langley and Stephanie Sage. 1994. Oblivious decision trees and abstract cases. In Working Notes of the AAAI-94 Workshop on Case-Based Reasoning. AAAI Press, 113--117."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000016"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2911451.2914763"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766462.2767733"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2911451.2914758"},{"key":"e_1_2_1_20_1","volume-title":"Computer Organization and Design","author":"Patterson David","unstructured":"David Patterson and John Hennessy . 2014. Computer Organization and Design ( 5 th ed.). Morgan Kaufmann . David Patterson and John Hennessy. 2014. Computer Organization and Design (5th ed.). Morgan Kaufmann.","edition":"5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000019"},{"key":"e_1_2_1_22_1","volume-title":"Machine learning in search quality at Yandex. Presentation at the industry track of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR).","author":"Segalovich Ilya","unstructured":"Ilya Segalovich . 2010. Machine learning in search quality at Yandex. Presentation at the industry track of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). Retrieved from http:\/\/download.yandex.ru\/company\/presentation\/yandex-sigir.ppt. (2010). Ilya Segalovich. 2010. Machine learning in search quality at Yandex. Presentation at the industry track of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). Retrieved from http:\/\/download.yandex.ru\/company\/presentation\/yandex-sigir.ppt. (2010)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88693-8_44"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609525"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2012.47"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000013087.49260.fb"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835449.1835475"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009934"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871452"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-009-9112-1"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 29th International Conference on Machine Learning (ICML). ACM, 1175--1182","author":"Xu Zhixiang","year":"2012","unstructured":"Zhixiang Xu , Kilian Weinberger , and Olivier Chapelle . 2012 . The greedy miser: Learning under test-time budgets . In Proceedings of the 29th International Conference on Machine Learning (ICML). ACM, 1175--1182 . Zhixiang Xu, Kilian Weinberger, and Olivier Chapelle. 2012. The greedy miser: Learning under test-time budgets. In Proceedings of the 29th International Conference on Machine Learning (ICML). ACM, 1175--1182."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939677"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2987380","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2987380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:38:37Z","timestamp":1750282717000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2987380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,12]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/2987380"],"URL":"https:\/\/doi.org\/10.1145\/2987380","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,12]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}