Patent ID: 8280915

Claim:
A method of generating a decision tree model in a computer system comprising a processor, a memory, and computer program instructions, which when executed by the processor perform the method comprising: generating a plurality of bitmaps in a database system, the bitmaps generated from data stored in a database table in the database system, the database table comprising a plurality of rows of data, the plurality of bitmaps comprising a bitmap for each unique value of each predictor and target and indicating whether or not that unique value of each predictor and target is present in each row of the database table; constructing a binary tree for a predictor that splits the values of the predictor into a plurality of portions, pruning the binary tree, defining as bins of the predictor leaves of the tree that remain after pruning, each leaf of the tree representing a portion of the values of the predictor, binning the predictor using the defined bins by replacing the portion of the values of the predictor represented by each leaf of the tree with a bin so as to reduce a cardinality of the predictor by reducing a number of distinct values of the predictor to a number of the bins; counting predictor-target pairs for each combination of binned predictor value and target value using the bitmaps; determining a splitter value for the data in the database table using the counts of the predictor-target pairs so as to split the data in the database table into a plurality of child nodes, each child node comprising a portion of the data in the database table; generating child bitmaps for the data in each child node; and recursively counting predictor-target pairs for each child node using the bitmaps, determining a splitter value for the data in each child node so as to split each child node into a plurality of new child nodes, and generating child bitmaps for the data in each new child node; whereby a decision tree model is formed including the predictor using the defined bins to reduce the cardinality of the predictor to the number of distinct values equal to the number of the bins in the decision tree model.