System and method for building decision tree classifiers using bitmap techniques

A method of generating a decision tree model comprising:

• generating a plurality of bitmaps in the 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;
• intersecting each split node bitmap with each predictor bitmap and with each target bitmap to form intersected bitmaps;
• counting bits of each intersected bitmap to generate a count of predictor-target pairs;
• 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;
• recursively generating a split node bitmap for each child node by intersecting a parent node bitmap and a bitmap of a predictor that satisfies a condition of the child node;
• intersecting each child node bitmap with each predictor bitmap and with each target bitmap to form intersected bitmaps;
• and
• counting bits of each intersected bitmap to generate a count of predictor-target pairs;
• whereby a decision tree model is formed.

A database system for counting predictor-target pairs for a decision tree model, the decision tree model based on data stored in a database, the data comprising a plurality of rows of data, at least one predictor and at least one target, the system comprising:

• a processor operable to execute computer program instructions;
• a memory operable to store computer program instructions executable by the processor;
• and
• computer program instructions stored in the memory and executable to perform the steps of:
• generating a split node bitmap for each split node of data stored in a database system by intersecting a parent node bitmap and a bitmap of a predictor that satisfies a condition of the node;
• intersecting each split node bitmap with each predictor bitmap and with each target bitmap to form intersected bitmaps;
• and
• counting bits of each intersected bitmap to generate a count of predictor-target pairs.

A database system for generating a decision tree model comprising:

• a processor operable to execute computer program instructions;
• a memory operable to store computer program instructions executable by the processor;
• and
• computer program instructions stored in the memory and executable to perform the steps of:
• generating a plurality of bitmaps in the 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;
• intersecting each split node bitmap with each predictor bitmap and with each target bitmap to form intersected bitmaps;
• counting bits of each intersected bitmap to generate a count of predictor-target pairs;
• 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;
• recursively generating a bitmap for each child node by intersecting a parent node bitmap and a bitmap of a predictor that satisfies a condition of the child node;
• intersecting each child node bitmap with each predictor bitmap and with each target bitmap to form intersected bitmaps;
• and
• counting bits of each intersected bitmap to generate a count of predictor-target pairs;
• whereby a decision tree model is formed.

A computer program product for counting predictor-target pairs for a decision tree model, the decision tree model based on data stored in a database, the data comprising a plurality of rows of data, at least one predictor and at least one target, the computer program product comprising:

• a computer readable medium;
• computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of:
• generating a split node bitmap for each split node of data stored in a database system by intersecting a parent node bitmap and a bitmap of a predictor that satisfies a condition of the node;
• intersecting each split node bitmap with each predictor bitmap and with each target bitmap to form intersected bitmaps;
• and
• counting bits of each intersected bitmap to generate a count of predictor-target pairs.

A computer program product for generating a decision tree model in a database system, comprising:

• a computer readable medium;
• computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of
• generating a plurality of bitmaps in the 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;
• intersecting each split node bitmap with each predictor bitmap and with each target bitmap to form intersected bitmaps;
• counting bits of each intersected bitmap to generate a count of predictor-target pairs;
• 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;
• recursively generating a bitmap for each child node by intersecting a parent node bitmap and a bitmap of a predictor that satisfies a condition of the child node;
• intersecting each child node bitmap with each predictor bitmap and with each target bitmap to form intersected bitmaps;
• and
• counting bits of each intersected bitmap to generate a count of predictor-target pairs;
• whereby a decision tree model is formed.