An efficient decision tree construction for large datasets

In this paper, we propose a new data structure and a new framework of building decision tree classifiers that is especially suitable for large datasets. The most prominent feature of our algorithm is that in order to build a decision tree, only one scan over the entire database is needed. Compared with previous methods, where at each level of the tree one scan over the whole database is made, our algorithm is obviously much more efficient. Moreover, our algorithm provides one-time sort process for numeric attributes, which significantly reduces the sorting cost and hence the whole execution time. The experimental results show that our algorithm outperforms the RainForest algorithm - a well-known and efficient algorithm for decision tree construction - in time dimension. This proves that our algorithm can be applied into large datasets efficiently.