Dynamic load balancing of unstructured computations in decision tree classifiers

One of the important problems in data mining is discov-ering classification models from datasets. Application do-mains include retail target marketing, fraud detection, and design of telecommunication service plans. Highly paral-lel algorithms for constructing classification decision trees are desirable for dealing with large data sets. Algorithms for building classification decision trees have a natural con-currency, but are difficult to parallelize due to the inher-ent dynamic nature of the computation. In this short pa-per, we present parallel formulations of classification de-cision tree learning algorithm based on induction. We de-scribe two basic parallel formulations, Synchronous Tree Construction Approach and Partitioned Tree Construction Approach. We propose a hybrid method that employs the good features of these methods. Our experimental results of the hybrid method on an IBM SP-2 demonstrate excellent speedups.