Decision Tree: SPRINT vs SLIQ?

Question

I found different types of decision trees, for example, SPRINT and SLIQ methods. Both methods are used for the classification problems, using Gini Index for the feature selection and following the procedure (according to this on slide 8):

1. Start Pre-sorting the samples.
2. As long as the stop criterion has not been reached: For every attribute: Place all nodes into a class histogram and Start evaluation of the splits.
3. Choose a split.
4. Update the decision tree; for each new node update its class list (nodes).

So, my question is: what is the difference between SPRINT and SLIQ algorithm?

Answer 1

SPRINT

It stands for the Scalable Parallelizable Induction of Decision Tree algorithm. It was introduced by Shafer et al in 1996. It is a fast, scalable decision tree classifier. It is not based on HUNT's Algorithm in constructing the decision tree, rather it partitions the training data set recursively using breadth-first greedy technique until each partition belongs to the same leaf node or class. It can be implemented in both serial and parallel pattern for good data placement and load balancing.

Unlike SLIQ, SPRINT uses two data structures; attribute list and histogram which is not memory resident, this implementation makes SPRINT more suitable for large data sets, thus it removes all the data memory restrictions on data. It handles both continuous and categorical attributes

SPRINT algorithm is a classical algorithm for building a decision tree that is a widely used method of data classification. However, the SPRINT algorithm has high computational cost in the calculation of attribute segmentation.

SLIQ Algorithm

It stands for Supervised Learning In Ques. It was introduced by Mehta et al (1996). It is a fast scalable decision tree algorithm that can be implemented in serial and parallel pattern. It is not based on HUNT'S Algorithm for decision tree classification. It partitions a training data set recursively using the breadth-first greedy strategy that is integrated with the pre-sorting technique during the tree building phase. In building a decision tree model SLIQ handles both numeric and categorical attributes

One of the main drawbacks of SLIQ is that it uses a class list data structure that is memory resident, thereby imposing memory restrictions on the data. It uses Minimum Description Length Principle(MDL) in pruning the tree after constructing it MDL is an inexpensive technique in tree pruning that uses the least amount of coding in producing trees that is small in size using the bottom-up technique.

The main advantage of the SLIQ decision tree algorithm is that it produces accurate decision trees that are significantly smaller than the trees produced using C4.5 and CART. At the same time, SLIQ executes nearly an order of magnitude faster than CART.

• SPRINT: A Scalable Parallel Classifier for Data Mining
• Comparative Analysis of Decision Tree Classification Algorithms
• A Searching Method of Candidate Segmentation Point in SPRINT Classification
• Decision Trees from large Databases: SLIQ
• A Comparative Study on Serial Decision Tree Classification Algorithms in Text Mining

Answer 2

SLIQ Algorithm It stands for supervised learning in ques. It is a fast scalable decision tree algorithm that can be implemented in a serial and parallel pattern.It partitions a training data set recursively using a breadth-first greedy strategy that is integrated with the pre-sorting technique during the tree building phase. In building a decision tree model SLIQ handles both numeric and categorical attributes. SPRINT is a new decision-tree-based classification algorithm that removes all of the memory restrictions and is fast and scalable. The algorithm has also been designed to be easily parallelized, allowing many processors to work together to build a single consistent model. SPRINT has excellent scale-up, speed-up, and size-up properties. The combination of these characteristics makes SPRINT an ideal tool for data mining. One of the disadvantages of SLIQ is that it uses a class a list data structure that is memory resident thereby imposing memory restrictions on the data. It uses the minimum description length principle(MDL) in pruning the tree after constructing it MDL is an expensive technique in tree pruning that uses the least amount of coding in producing a tree that is small in size using the bottom-up technique. SPRINT has no restriction on the size of the input and yet is a fast algorithm. It shares with SLIQ the advantage of a one-time sort but uses different data structures.