High Throughput Hardware for Hoeffding Tree Algorithm with Adaptive Naive Bayes Predictor

摘要

Hoeffding tree algorithm is a popular online decision tree algorithm capable of learning from huge data streams. The algorithm involves complex time consuming computations in the leaves of the tree for each data instance. These computations involve a lot of parallelisms which can be exploited and implemented in a field programmable gate array to achieve speedup. This paper presents a hardware accelerator for Hoeffding tree algorithm with adaptive naive bayes predictor in the leaves. The proposed system is capable of accelerating data streams with both nominal and numeric attributes using minimum hardware resources for huge datasets. It is implemented on a Xilinx VC707 board based on Virtex-7 XC7VX485T field programmable gate array. The implemented system is about 9x faster than StreamDm(C++), a well known reference software implementation for the standard forest cover type dataset.