Parallel tree based prediction

A computer program product for performing an ensemble model based prediction for a set of input data records, the ensemble model comprising a plurality of trees comprising decision trees or regression trees, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processing circuit to cause the processing circuit to:

• create, for each of the trees in the ensemble model, an assignment table, each assignment table assigning all data records in the input data set to a root node of said tree, in a database management system that is in control of a plurality of processing units and of a plurality of data slices, the database management system being operable to process data stored in any one of the data slices by a respective one of the processing units;
• split each of the assignment tables into disjoint sub-tables;
• store each of the sub-tables to a respective one of the data slices;
• designate root nodes of each of the plurality of trees as a set of current nodes corresponding to a current level of all the trees;
• execute in parallel until all of the assignment tables are assigned to leaf nodes of the plurality of trees, by all processing units whose respective data slice comprises one or more of the sub-tables:
• performing a single pass through the sub-tables stored in the data slice of said processing unit, thereby identifying one or more of the current nodes having been assigned to one or more of the data records of said data slice;
• evaluating split conditions of each of the identified current nodes on the data records assigned to said current node;
• based on said evaluation, de-assigning input data records from each of said current nodes and re-assigning said input data records to one or more of the child-nodes of said current node;
• using the child nodes of all current nodes as the set of current nodes corresponding to the current level of each of the plurality of trees;
• and
• calculating a prediction result from the assignment of data records to the leaf nodes of each of the plurality of trees.

A computer system for performing an ensemble model based prediction for a set of input data records, the ensemble model comprising a plurality of trees comprising decision trees or regression trees, the system comprising:

• a memory;
• and
• a processor, communicatively coupled to said memory, the computer system configured to perform a method comprising:
• creating, for each of the trees in the ensemble model, an assignment table, each assignment table assigning all data records in the input data set to a root node of said tree, in a database management system that is in control of a plurality of processing units and of a plurality of data slices, the database management system being operable to process data stored in any one of the data slices by a respective one of the processing units;
• splitting each of the assignment tables into disjoint sub-tables;
• storing each of the sub-tables to a respective one of the data slices;
• designating root nodes of each of the plurality of trees as a set of current nodes corresponding to a current level of all the trees;
• executing in parallel until all of the assignment tables are assigned to leaf nodes of the plurality of trees, by all processing units whose respective data slice comprises one or more of the sub-tables:
• performing a single pass through the sub-tables stored in the data slice of said processing unit, thereby identifying one or more of the current nodes having been assigned to one or more of the data records of said data slice;
• evaluating split conditions of each of the identified current nodes on the data records assigned to said current node;
• based on said evaluation, de-assigning input data records from each of said current nodes and re-assigning said input data records to one or more of the child-nodes of said current node;
• using the child nodes of all current nodes as the set of current nodes corresponding to the current level of each of the plurality of trees;
• and
• calculating a prediction result from the assignment of data records to the leaf nodes of each of the plurality of trees.