Parallel classification for data mining in a shared-memory multiprocessor system

A computer program product for use with a shared-memory multiprocessor system for generating a decision-tree classifier from a set of records, the tree having a plurality of nodes, the product comprising:

• a computer-readable medium;
• means, provided on the computer-readable medium, for directing the processors to cooperatively generate in the shared memory an attribute list for each attribute of the records, the attribute lists corresponding a current node and including tuples each having information on a record class;
• means, provided on the computer-readable medium, for directing the system to assign each attribute list of the current node to one of the processors;
• means, provided on the computer-readable medium, for directing each processor to access the attribute lists assigned to the processor, in the shared memory, and determine a best split for each attribute list;
• means, provided on the computer-readable medium, for directing the processors to cooperatively determine, through the shared memory, a global best split for all the attribute lists associated with the current node;
• means, provided on the computer-readable medium, for directing the processors to reassign each attribute list of the current node to one of the processors;
• means, provided on the computer-readable medium, for directing each processor to split the attribute lists reassigned to the processor according to the global best split into new attribute lists, the new lists corresponding to child nodes of the current node and residing in the shared memory;
• and
• means provided on the computer-readable medium, for directing the processors to process each newly created child node as the current node, until each attribute list for the newly child nodes includes only tuples of the same record class.

A database system for generating a decision-tree classifier in a shared-memory multiprocessor computer from a set of records, the tree having a plurality of nodes, the system comprising:

• means for generating cooperatively by the processors, in the shared memory, an attribute list for each attribute of the records, the attribute lists corresponding a current node and including tuples each having information on a record class;
• means for assigning each attribute list of the current node to one of the processors;
• means for accessing the attribute lists in the shared memory, by each processor, to determine a best split for each attribute list;
• means for cooperatively determining by the processors, through the shared memory, a global best split for all the attribute lists associated with the current node;
• means for reassigning each attribute list of the current node to one of the processors;
• means for splitting, by each processor, the reassigned attribute lists according to the global best split into new attribute lists, the new lists corresponding to child nodes of the current node and residing in the shared memory;
• and
• means for processing each newly created child node as the current node, until each attribute list for the newly created child nodes includes only tuples of the same record class.