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

Claim 3

The method as recited in claim 1 , wherein the steps (b)-(f) are repeated with each newly created child node as the current node, until each attribute list for the newly created child nodes includes no more than a predetermined number of tuples.

Claim 4

The method as recited in claim 1 , wherein the classifier is a multilevel tree structure, and each level has a plurality of nodes.

Claim 5

The method as recited in claim 1 , wherein each processor accesses the assigned attribute lists for all of the nodes at the same level of the tree only once in determining the respective best splits.

Claim 6

The method as recited in claim 4 , wherein a shared variable is used to dynamically synchronize the assignment of the attribute lists to the processors.

Claim 7

The method as recited in claim 5 , wherein the assignment of the attribute lists to the processors is the same for all of the nodes at the same level of the tree.

Claim 8

The method as recited in claim 1 , wherein each processor accesses the reassigned attribute lists for all of the nodes at the same level of the tree only once in splitting the reassigned lists.

Claim 9

The method as recited in claim 7 , wherein a shared variable is used to dynamically synchronize the reassignment of the attribute lists to processors.

Claim 10

The method as recited in claim 8 , wherein the reassignment of the attribute lists to processors is the same for all of the nodes at the same level of the tree.

Claim 11

The method as recited in claim 1 , further comprising the step of building a data structure to determine whether a tuple of an attribute list belongs to a left child attribute list or a right child attribute list.

Claim 12

The method as recited in claim 10 , wherein: the classifier is a multilevel tree structure, each level having a plurality of nodes; the method further comprises the step of creating, for every K consecutive nodes at the same level of the tree, K different files for storing the attribute lists of the K nodes; and the determination of the best splits for the respective attribute lists of the K nodes and the building of the data structure for the K nodes are done in parallel by each processor.

Claim 13

The method as recited in claim 11 , wherein a barrier synchronization between two groups of K nodes is used to prevent any two processors from simultaneously accessing a same file.

Claim 14

The method as recited in claim 11 , wherein K conditional variables are used to prevent any two processors from simultaneously accessing a same file.

Claim 15

The method as recited in claim 1 , wherein: all processors of the system are initially associated with the current node; the processors to which the attribute lists are assigned and reassigned are selected from the processors associated with the current node; and when the child nodes are created from the current node, the processors associated with the current node are divided into two subsets, each associated with a child node.

Claim 16

The method as recited in claim 14 , wherein: a processor becomes free when all the nodes associated with the processor can no longer be split; and the free processor would join the other processors in processing the attributes lists for other nodes.

Claim 17

The method as recited in claim 1 , further comprising the step of pruning the decision-tree classifier to obtain a more compact classifier.

Claim 18

The method as recited in claim 16 , wherein the step of pruning is based on a Minimum Description Length model of the classifier.

Claim 19

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.

Claim 20

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.

Claim 21

The computer program product as recited in claim 18 , wherein the each newly created child node is processed as the current node until each attribute list for the newly created child nodes includes no more than a predetermined number of tuples.

Claim 22

The computer program product as recited in claim 18 , wherein the classifier is a multilevel tree structure, and each level has a plurality of nodes.

Claim 23

The computer program product as recited in claim 18 , wherein each processor accesses the respective assigned attribute lists for all of the nodes at the same level of the tree only once in determining the respective best splits.

Claim 24

The computer program product as recited in claim 21 , wherein a shared variable is used to dynamically synchronize the assignment of the attribute lists to the processors.

Claim 25

The computer program product as recited in claim 22 , wherein the assignment of the attribute lists to the processors is the same for all of the nodes at the same level of the tree.

Claim 26

The computer program product as recited in claim 18 , wherein each processor accesses the reassigned attribute lists for all of the nodes at the same level of the tree only once in splitting the reassigned lists.

Claim 27

The computer program product as recited in claim 24 , wherein a shared variable is used to dynamically synchronize the reassignment of the attribute lists to processors.

Claim 28

The computer program product as recited in claim 25 , wherein the reassignment of the attribute lists to processors is the same for all of the nodes at the same level of the tree.

Claim 29

The computer program product as recited in claim 18 , further comprising means, provided on the computer-readable medium, for directing the system to build a data structure to determine whether a tuple of an attribute list belongs to a left child attribute list or a right child attribute list.

Claim 30

The computer program product as recited in claim 27 , wherein: the classifier is a multilevel tree structure, each level having a plurality of nodes; the computer program product further comprises means, provided on the computer-readable medium, for directing the system to create, for every K consecutive nodes at the same level of the tree, K different files for storing the attribute lists of the K nodes; and the determination of the best splits for the respective attribute lists of the K nodes and the building of the data structure for the K nodes are done in parallel by each processor.

Claim 31

The computer program product as recited in claim 28 , wherein a barrier synchronization between two groups of K nodes is used to prevent any two processors from simultaneously accessing a same file.

Claim 32

The computer program product as recited in claim 28 , wherein K conditional variables are used to prevent any two processors from simultaneously accessing a same file.

Claim 33

The computer program product as recited in claim 18 , wherein: all processors of the system are initially associated with the current node; the processors to which the attribute lists are assigned and reassigned are selected from the processors associated with the current node; and when the child nodes are created from the current node, the processors associated with the current node are divided into two subsets, each associated with a child node.

Claim 34

The computer program product as recited in claim 31 , wherein: a processor becomes free when all the nodes associated with the processor can no longer be split; and the free processor would join the other processors in processing the attributes lists for other nodes.

Claim 35

The computer program product as recited in claim 18 , further comprising means, provided on the computer-readable medium, for directing the system to prune the decision-tree classifier to obtain a more compact classifier.

Claim 36

The computer program product as recited in claim 33 , wherein the pruning is based on a Minimum Description Length model of the classifier.

Claim 37

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.

Claim 38

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.

Claim 39

The system as recited in claim 35 , wherein each newly created child node is processed as the current node until each attribute list for the newly created child nodes includes no more than a predetermined number of tuples.

Claim 40

The system as recited in claim 35 , wherein the classifier is a multilevel tree structure, and each level has a plurality of nodes.

Claim 41

The system as recited in claim 35 , wherein each processor accesses the assigned attribute lists for all of the nodes at the same level of the tree only once in determining the respective best splits.

Claim 42

The system as recited in claim 38 , wherein a shared variable is used to dynamically synchronize the assignment of the attribute lists to the processors.

Claim 43

The system as recited in claim 39 , wherein the assignment of the attribute lists to the processors is the same for all of the nodes at the same level of the tree.

Claim 44

The system as recited in claim 35 , wherein each processor accesses the reassigned attribute lists for all of the nodes at the same level of the tree only once in splitting the reassigned lists.

Claim 45

The system as recited in claim 41 , wherein a shared variable is used to dynamically synchronize the reassignment of the attribute lists to processors.

Claim 46

The system as recited in claim 42 , wherein the reassignment of the attribute lists to processors is the same for all of the nodes at the same level of the tree.

Claim 47

The system as recited in claim 35 , further comprising means for building a data structure to determine whether a tuple of an attribute list belongs to a left child attribute list or a right child attribute list.

Claim 48

The system as recited in claim 44 , wherein the classifier is a multilevel tree structure, each level having a plurality of nodes; the system further comprises means for creating, for every K consecutive nodes at the same level of the tree, K different files for storing the attribute lists of the K nodes; and the determination of the best splits for the respective attribute lists of the K nodes and the building of the data structure for the K nodes are done in parallel by each processor.

Claim 49

The system as recited in claim 45 , wherein a barrier synchronization between two groups of K nodes is used to prevent any two processors from simultaneously accessing a same file.

Claim 50

The system as recited in claim 45 , wherein K conditional variables are used to prevent any two processors from simultaneously accessing a same file.

Claim 51

The system as recited in claim 35 , wherein: all processors of the computer are initially associated with the current node; the processors to which the attribute lists are assigned and reassigned are selected from the processors associated with the current node; and when the child nodes are created from the current node, the processors associated with the current node are divided into two subsets, each associated with a child node.

Claim 52

The system as recited in claim 48 , wherein: a processor becomes free when all the nodes associated with the processor can no longer be split; and the free processor would join the other processors in processing the attributes lists for other nodes.

Claim 53

The system as recited in claim 35 , further comprising means for pruning the decision-tree classifier to obtain a more compact classifier.

Claim 54

The system as recited in claim 50 wherein the means for pruning is based on a Minimum Description Length model of the classifier.