Compact hash tables for decision-trees

• We provide a conversion technique from decision-trees to compact hash tables.
• We evaluate the performance on FPGA and multi-core platforms, respectively.
• We achieve high speedups using our techniques on various platforms.

Decision-trees have been widely used in scientific computing. It is challenging to sustain high performance for large decision-trees. In this paper, we present a conversion technique translating a generic decision-tree into multiple compact hash tables; the conversion technique does not depend on the depth or shape of the decision-tree. All the compact hash tables are searched individually; the outcomes from all the tables are merged into the final result. To evaluate the performance, we prototype our design on state-of-the-art FPGA and multi-core General Purpose Processors (GPPs). Experimental results show that, for a typical 92-leaf decision-tree, we achieve 533 Million Classifications Per Second (MCPS) throughput and 26 ns latency on FPGA, and 134 MCPS throughput and 239 ns latency on multi-core GPP. We sustain 6 × and 2.7 × speedups, respectively.