{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T06:49:49Z","timestamp":1775544589787,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T00:00:00Z","timestamp":1666051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Federal Ministry of Education and Research of Germany as part of the competence center for machine learning ML2R","award":["01IS18038A"],"award-info":[{"award-number":["01IS18038A"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["405422836 and 124020371"],"award-info":[{"award-number":["405422836 and 124020371"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Deutscher Akademischer Austauschdienst (DAAD) within the Programme for Project-Related Personal Exchange","award":["57559723"],"award-info":[{"award-number":["57559723"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2022,11,30]]},"abstract":"<jats:p>For timing-sensitive edge applications, the demand for efficient lightweight machine learning solutions has increased recently. Tree ensembles are among the state-of-the-art in many machine learning applications. While single decision trees are comparably small, an ensemble of trees can have a significant memory footprint leading to cache locality issues, which are crucial to performance in terms of execution time. In this work, we analyze memory-locality issues of the two most common realizations of decision trees, i.e., native and if-else trees. We highlight that both realizations demand a more careful memory layout to improve caching behavior and maximize performance. We adopt a probabilistic model of decision tree inference to find the best memory layout for each tree at the application layer. Further, we present an efficient heuristic to take architecture-dependent information into account thereby optimizing the given ensemble for a target computer architecture. Our code-generation framework, which is freely available on an open-source repository, produces optimized code sessions while preserving the structure and accuracy of the trees. With several real-world data sets, we evaluate the elapsed time of various tree realizations on server hardware as well as embedded systems for Intel and ARM processors. Our optimized memory layout achieves a reduction in execution time up to 75 % execution for server-class systems, and up to 70 % for embedded systems, respectively.<\/jats:p>","DOI":"10.1145\/3508019","type":"journal-article","created":{"date-parts":[[2022,1,26]],"date-time":"2022-01-26T18:20:38Z","timestamp":1643221238000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Efficient Realization of Decision Trees for Real-Time Inference"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7110-921X","authenticated-orcid":false,"given":"Kuan-Hsun","family":"Chen","sequence":"first","affiliation":[{"name":"University of Twente, Enschede, Netherlands"}]},{"given":"Chiahui","family":"Su","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Hsinchu, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9992-9415","authenticated-orcid":false,"given":"Christian","family":"Hakert","sequence":"additional","affiliation":[{"name":"Technical University of Dortmund, Dortmund, Germany"}]},{"given":"Sebastian","family":"Buschj\u00e4ger","sequence":"additional","affiliation":[{"name":"Technical University of Dortmund, Dortmund, Germany"}]},{"given":"Chao-Lin","family":"Lee","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Hsinchu, Taiwan"}]},{"given":"Jenq-Kuen","family":"Lee","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Hsinchu, Taiwan"}]},{"given":"Katharina","family":"Morik","sequence":"additional","affiliation":[{"name":"Technical University of Dortmund, Dortmund, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8114-9760","authenticated-orcid":false,"given":"Jian-Jia","family":"Chen","sequence":"additional","affiliation":[{"name":"Technical University of Dortmund, Dortmund, Germany"}]}],"member":"320","published-online":{"date-parts":[[2022,10,18]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.73"},{"key":"e_1_3_2_3_2","first-page":"1063","article-title":"Analysis of a random forests model","volume":"13","author":"Biau G.","year":"2012","unstructured":"G. Biau. 2012. Analysis of a random forests model. Journal of Machine Learning Research 13, Apr (2012), 1063\u20131095.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11749-016-0481-7"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1692"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00058655"},{"key":"e_1_3_2_7_2","unstructured":"L. Breiman. 1996. Bias variance and arcing classifiers."},{"key":"e_1_3_2_8_2","volume-title":"Some Infinity Theory for Predictor Ensembles","author":"Breiman L.","year":"2000","unstructured":"L. Breiman. 2000. Some Infinity Theory for Predictor Ensembles. Technical Report. Technical Report 579, Statistics Dept. UCB."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010933404324"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00017"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2017.2710627"},{"key":"e_1_3_2_12_2","volume-title":"26th Astronomical Data Analysis Software and Systems Conference (ADASS)","author":"Buss Jens","year":"2016","unstructured":"Jens Buss, Christian Bockermann, Katharina Morik, Wolfgang Rhode, and Tim Ruhe. 2016. FACT-Tools \u2013 Processing high-volume telescope data. In 26th Astronomical Data Analysis Software and Systems Conference (ADASS). ADASS."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2987380"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/349214.349233"},{"key":"e_1_3_2_15_2","volume-title":"International Conference on Machine Learning (ICML)","author":"Denil M.","year":"2014","unstructured":"M. Denil, D. Matheson, and N. De Freitas. 2014. Narrowing the gap: Random forests in theory and in practice. In International Conference on Machine Learning (ICML)."},{"key":"e_1_3_2_16_2","unstructured":"Ulrich Drepper. 2007. What Every Programmer Should Know About Memory."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.14"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-012-0549-0"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-6226-1"},{"key":"e_1_3_2_21_2","unstructured":"T. Gleixner and I. Molnar. 2012. Perf: Linux profiling with performance counters. https:\/\/perf.wiki.kernel.org\/index.php\/Main_Page. Accessed: 2021-05-31."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/NVMSA51238.2020.9188136"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18074.2021.9586167"},{"key":"e_1_3_2_24_2","volume-title":"Computer Architecture, Fifth Edition: A Quantitative Approach (5th ed.)","author":"Hennessy John L.","year":"2011","unstructured":"John L. Hennessy and David A. Patterson. 2011. Computer Architecture, Fifth Edition: A Quantitative Approach (5th ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36574-5_10"},{"key":"e_1_3_2_27_2","volume-title":"Exploration of Cyber-physical Systems for GPGPU Computer Vision-based Detection of Biological Viruses","author":"Libuschewski Pascal","year":"2017","unstructured":"Pascal Libuschewski. 2017. Exploration of Cyber-physical Systems for GPGPU Computer Vision-based Detection of Biological Viruses. Ph.D. Dissertation. Technical University of Dortmund, Germany. http:\/\/hdl.handle.net\/2003\/35929."},{"key":"e_1_3_2_28_2","unstructured":"M. Lichman. 2013. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml."},{"key":"e_1_3_2_29_2","article-title":"Understanding random forests: From theory to practice","author":"Louppe G.","year":"2014","unstructured":"G. Louppe. 2014. Understanding random forests: From theory to practice. arXiv preprint arXiv:1407.7502 (2014).","journal-title":"arXiv preprint arXiv:1407.7502"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2766462.2767733"},{"key":"e_1_3_2_31_2","first-page":"383","volume-title":"Procs. ECML PKDD 2017","author":"Lucchese Claudio","year":"2017","unstructured":"Claudio Lucchese, Franco Maria Nradini, Salvatore Orlando, Raffaele Perego, Nicola Tonellotto, and Rossano Venturini. 2017. QuickScorer: Efficient traversal of large ensembles of decision trees. In Procs. ECML PKDD 2017. Springer, 383\u2013387."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2911451.2914758"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2013.322"},{"key":"e_1_3_2_34_2","first-page":"899","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Nakandala Supun","year":"2020","unstructured":"Supun Nakandala, Karla Saur, Gyeong-In Yu, Konstantinos Karanasos, Carlo Curino, Markus Weimer, and Matteo Interlandi. 2020. A tensor compiler for unified machine learning prediction serving. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 899\u2013917."},{"key":"e_1_3_2_35_2","first-page":"173","volume-title":"Procs. 4th Workshop on Mining and Learning with Graphs (MLG)","author":"Nijssen Siegfried","year":"2006","unstructured":"Siegfried Nijssen and Joost N. Kok. 2006. Frequent subgraph mines: Runtimes don\u2019t say everything. In Procs. 4th Workshop on Mining and Learning with Graphs (MLG). 173\u2013180."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.2172\/1078539"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2016.7472068"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2980765.2980768"},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1109\/FCCM.2012.47","volume-title":"Field-Programmable Custom Computing Machines (FCCM), 2012 IEEE 20th Annual International Symposium","author":"Essen B. Van","year":"2012","unstructured":"B. Van Essen, C. Macaraeg, M. Gokhale, and R. Prenger. 2012. Accelerating a random forest classifier: Multi-core, GP-GPU, or FPGA?. In Field-Programmable Custom Computing Machines (FCCM), 2012 IEEE 20th Annual International Symposium. IEEE, 232\u2013239."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.3390\/s19194138"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219857"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508019","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3508019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:18Z","timestamp":1750183818000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,18]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,11,30]]}},"alternative-id":["10.1145\/3508019"],"URL":"https:\/\/doi.org\/10.1145\/3508019","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,18]]},"assertion":[{"value":"2021-06-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}