Computer system and computerized method for partitioning data for parallel processing

• US 5,909,681 A
• Filed: 03/25/1996
• Issued: 06/01/1999
• Est. Priority Date: 03/25/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: Ascential Systems, Inc. (International Business Machines Corporation)
• Inventors: Zyszkowski, Edward S. A., Beckerle, Michael J., Passera, Anthony, Thorp, John R.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/624,844
• Time in Patent Office: 1,163 Days
• Field of Search: 395/603, 395/604, 395/608, 395/610, 395/613, 707/3, 707/6, 707/8, 707/10, 704/232, 706/16
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1858 Parallel file systems, i.e. file systems supporting multiple processors
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06V 10/94 Hardware or software architectures specially adapted for image or video understanding
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A computer system splits a data space to partition data between processors or processes. The data space may be split into sub-regions which need not be orthogonal to the axes defined by the data space'"'"'s parameters, using a decision tree. The decision tree can have neural networks in each of its non-terminal nodes that are trained on, and are used to partition, training data. Each terminal, or leaf, node can have a hidden layer neural network trained on the training data that reaches the terminal node. The training of the non-terminal nodes'"'"' neural networks can be performed on one processor and the training of the leaf nodes'"'"' neural networks can be run on separate processors. Different target values can be used for the training of the networks of different non-terminal nodes. The non-terminal node networks may be hidden layer neural networks. Each non-terminal node automatically may send a desired ratio of the training records it receives to each of its child nodes, so the leaf node networks each receives approximately the same number of training records. The system may automatically configures the tree to have a number of leaf nodes equal to the number of separate processors available to train leaf node networks. After the non-terminal and leaf node networks have been trained, the records of a large data base can be passed through the tree for classification or for estimation of certain parameter values.

Claims

1. A computer system comprising:

P processors, where P is an integer greater than one;

means for receiving a data set of data objects having N parameters, where N is an integer greater than one;

means for dividing an N-dimensional data space having a separate dimension of each of said N parameters into M sub-spaces, each corresponding to a region of said N-dimensional space, where M is an integer greater than or equal to P, so each of said data set'"'"'s data objects is located in one of said M sub-spaces, said means for dividing including means for dividing said space along boundaries which are non-orthogonal to said N dimensions; and

means for associating different ones of said sub-spaces with different ones of said processors, such that each of said P processors has a different set of one or more of said sub-spaces associated with it, including;

means for distributing the sub-set of data objects located in each sub-space to the processor associated with that sub-space; and

means for causing each processor to perform a computational process on each of the data objects so distributed to said processor.

2. A computer system comprising:

P parallel processors, where P is greater than one;

means for receiving a first data set of data objects to be processed;

d-tree means including;

means for storing a decision tree data structure having a plurality of non-terminal nodes, including a root node, and terminal nodes, wherein each of said non-terminal nodes has a plurality of child nodes, each of which is either one of said non-terminal or terminal nodes;

means for storing a trainable decision criterion for each of said non-terminal nodes; and

means for training said decision tree including;

means for supplying a second set of said data objects to said root node as a training set, wherein said second set can either be equal to or different than said first set; and

means for performing the following operation for each given non-terminal node in said tree;

causing each given non-terminal node to use those of said training set data objects supplied to it to train said given node'"'"'s decision criterion; and

supplying each training set data object supplied to the given node to one of the given node'"'"'s child nodes based on the application of the given node'"'"'s decision criteria to the data object, once the given node'"'"'s decision criteria has been trained; and

means for using said decision tree to partition said first data set into at least M data sub-sets, where M is equal or greater than P;

means for associating a different set of one or more of said data sub-sets with each of said P processors;

means for distributing the data objects in each data sub-set to the processor associated with that sub-set; and

means for causing each of said processors to perform a computational process on each of said data objects so distributed to the processor.

3. A computer system as in claim 2 wherein said d-tree means performs the process of partitioning said first data set on less than one half the P processors when P is more than 2.

4. A computer system as in claim 2 wherein said training data set is a sub-set of said first data set.

5. A computer system as in claim 2 wherein said decision criterion associated with one or more of said non-terminal nodes is a neural network.

7. A computer system as in claim 2 wherein the d-tree means further includes means for automatically setting the decision criteria of individual non-terminal nodes of the decision tree so as to achieve a desired ratio between the number of data objects supplied to each such node'"'"'s child nodes.

6. A computer system comprising:

P parallel processors, where P is greater than one;

means for receiving a first data set of data objects to be processed;

d-tree means for using a decision tree to partition said first data set into at least M data sub-sets, where M is equal or greater than P;

means for associating a different set of one or more of said data sub-sets with each of said P processors;

means for distributing the data objects in each data sub-set to the processor associated with that sub-set; and

means for causing each of said processors to perform a computational process on each of said data objects so distributed to the processor;

wherein said d-tree means includes;

means for storing a decision tree data structure having a plurality of non-terminal nodes, including a root node, and terminal nodes, wherein each of said non-terminal nodes has a plurality of child nodes, each of which is either one of said non-terminal or terminal nodes;

means for storing a trainable decision criterion for each of said non-terminal nodes; and

means for training said decision tree including;

means for supplying a second set of said data objects to said root node as a training set, wherein said second set can either be equal to or different than said first set; and

means for performing the following operation for each given non-terminal node in said tree;

causing each given non-terminal node to use those of said training set data objects supplied to it to train said given node'"'"'s decision criterion;

supplying each training set data object supplied to the given node to one of the given node'"'"'s child nodes based on the application of the given node'"'"'s decision criteria to the data object, once the given node'"'"'s decision criteria has been trained; and

wherein the decision criterion associated with one or more of said non-terminal nodes is a neural network and the decision criterion associated with at least one of said non-terminal node has a hidden layer.

8. A computer system comprising:

P parallel processors, where P is greater than one;

means for receiving a first data set of data objects to be processed;

d-tree means for using a decision tree to partition said first data set into at least M data sub-sets, where M is equal or greater than P;

means for associating a different set of one or more of said data sub-sets with each of said P processors;

means for distributing the data objects in each data sub-set to the processor associated with that sub-set; and

means for causing each of said processors to perform a computational process on each of said data objects so distributed to the processor;

wherein said d-tree means includes;

means for storing a decision tree data structure having a plurality of non-terminal nodes, including a root node, and terminal nodes, wherein each of said non-terminal nodes has a plurality of child nodes, each of which is either one of said non-terminal or terminal nodes;

means for storing a trainable decision criterion for each of said non-terminal nodes;

means for training said decision tree including;

means for supplying a second set of said data objects to said root node as a training set, wherein said second set can either be equal to or different than said first set; and

means for performing the following operation for each given non-terminal node in said tree;

causing each given non-terminal node to use those of said training set data objects supplied to it to train said given node'"'"'s decision criterion;

supplying each training set data object supplied to the given node to one of the given node'"'"'s child nodes based on the application of the given node'"'"'s decision criteria to the data object, once the given node'"'"'s decision criteria has been trained; and

means for automatically setting the decision criteria of individual non-terminal nodes of the decision tree so as to achieve a desired ratio between the number of data objects supplied to each such node'"'"'s child nodes; and

means for automatically configuring the decision tree used so that it has P times I end nodes, where I is an integer, each of which end nodes defines one of said data sub-sets.

9. A computer system comprising:

means for receiving a data set of data objects having N parameters associated with them, where N is an integer greater than one;

means for dividing an N-dimensional data space having a separate dimension for each of said N parameters into M sub-spaces, each corresponding to a region of said N-dimensional space, where M is an integer greater than one, so each of said data set'"'"'s data objects is located in one of said M sub-spaces;

means for representing each of M hidden layer neural networks;

means for associating each of the M sub-spaces with one of said M neural networks; and

means for using the data objects in each of said M sub-spaces to train that sub-space'"'"'s associated hidden layer neural network.

10. A computer system as in claim 9 wherein said means for dividing including means for dividing said space along boundaries which are non-orthogonal to said N dimensions.

11. A computerized method including:

receiving a first data set comprised of a plurality of data objects; and

creating a decision tree data structure having a plurality of non-terminal nodes, including a root node, and terminal nodes, wherein each of said non-terminal nodes has a plurality of child nodes, each of which is either one of said non-terminal or terminal nodes, said creating of a decision tree including;

creating for each non-terminal node a neural network;

creating for each terminal node a neural network containing at least one hidden layer;

supplying a second data set of data objects to said root node as a training set, wherein said second data set can either be equal to or different than said first data set;

performing the following operation for each given non-terminal node in said tree;

using the training set data objects supplied to the given non-terminal node to train the given node'"'"'s neural network; and

supplying each data object of said first and second data sets supplied to the given node to one of the given node'"'"'s child nodes based on the output of the given node'"'"'s neural network for the data object, once the given node'"'"'s neural net has been trained; and

using said data objects of the first data set supplied to a given terminal node to train the given terminal node'"'"'s hidden layer neural network.

12. A computerized method as in claim 11 wherein:

the data objects have N parameters associated with them, where N is an integer greater than one;

said using of training set data objects supplied to the given non-terminal node includes using said data objects to train the given non-terminal node'"'"'s neural network to develop spatial criteria for dividing an N-dimensional data space having a separate dimension for each of said N parameters into a separate sub-space for each of the given non-terminal node'"'"'s child nodes, each of which sub-spaces corresponds to a region of said N-dimensional space, so that each of said data objects supplied to the given node is located in one of said sub-spaces; and

said supplying of data objects to a one of a given node'"'"'s child nodes is based on the given node'"'"'s neural network'"'"'s spatial criteria, such that data objects from different sub-spaces of said N-dimensional space are supplied to different ones of the given node'"'"'s child nodes.

14. A computerized method as in claim 11 wherein said using of training set data objects supplied to a given terminal node includes using such data objects supplied to each of a plurality of said terminal nodes to train said terminal node'"'"'s associated hidden layer neural network on a different parallel processor.

16. A computerized method as in claim 11 wherein one or more of said non-terminal node'"'"'s neural networks have hidden layers.

13. A computerized method including:

receiving a first data set comprised of a plurality of data objects; and

creating a decision tree data structure having a plurality of non-terminal nodes, including a root node, and terminal nodes, wherein each of said non-terminal nodes has a plurality of child nodes, each of which is either one of said non-terminal or terminal nodes, said creating of a decision tree including;

creating for each non-terminal node a neural network;

creating for each terminal node a neural network containing at least one hidden layer;

supplying a second data set of data objects to said root node as a training set, wherein said second data set can either be equal to or different than said first data set;

performing the following operation for each given non-terminal node in said tree;

using the training set data objects supplied to the given non-terminal node to train the given node'"'"'s neural network; and

supplying each data object of said first and second data sets supplied to the given node to one of the given node'"'"'s child nodes based on the output of the given node'"'"'s neural network for the data object, once the given node'"'"'s neural net has been trained; and

using said data objects of the first data set supplied to a given terminal node to train the given terminal node'"'"'s hidden layer neural network;

wherein;

the data objects have N parameters associated with them, where N is an integer greater than one;

said using of training set data objects supplied to the given non-terminal node includes using said data objects to train the given non-terminal node'"'"'s neural network to develop spatial criteria for dividing an N-dimensional data space having a separate dimension for each of said N parameters into a separate sub-space for each of the given non-terminal node'"'"'s child nodes, each of which sub-spaces corresponds to a region of said N-dimensional space, so that each of said data objects supplied to the given node is located in one of said sub-spaces;

said supplying of data objects to a one of a given node'"'"'s child nodes is based on the given node'"'"'s neural network'"'"'s spatial criteria, such that data objects from different sub-spaces of said N-dimensional space are supplied to different ones of the given node'"'"'s child nodes;

said creating of a neural network for each non-terminal node includes creating a two layer neural network for such a non-terminal node, each of which has a plurality of inputs, no hidden layers, an output, and a series of weights between each input and said output, which weights define a vector in said N-dimensional space; and

said supplying of each given one of a plurality of training set data objects to one of a given non-terminal node'"'"'s child nodes is based on which side of an N-dimensional plan perpendicular to said vector in said N-dimensional space that a given data object is located.

15. A computerized method including:

receiving a first data set comprised of a plurality of data objects; and

creating a decision tree data structure having a plurality of non-terminal nodes, including a root node, and terminal nodes, wherein each of said non-terminal nodes has a plurality of child nodes, each of which is either one of said non-terminal or terminal nodes, said creating of a decision tree including;

creating for each non-terminal node a neural network;

creating for each terminal node a neural network containing at least one hidden layer;

supplying a second data set of a data objects to said root node as a training set, wherein said second data set can either be equal to or different than said first data set; and

performing the following operation for each given non-terminal node in said tree;

using the training set data objects supplied to the given non-terminal node to train the given node'"'"'s neural network; and

supplying each data object of said first and second data sets supplied to the given node to one of the given node'"'"'s child nodes based on the output of the given node'"'"'s neural network for the data object, once the given node'"'"'s neural net has been trained;

using said data objects of the first data set supplied to a given terminal node to train the given terminal node'"'"'s hidden layer neural network, including using such data objects supplied to each of a plurality of said terminal nodes to train said terminal node'"'"'s associated hidden layer neural network on a different parallel processor;

storing a copy of said decision tree, including the neural networks in its non-terminal and terminal nodes on each of a plurality of processors;

dividing a set of data objects not in said training set into a plurality of data partitions, for each of said processors; and

passing the data objects in each given processor'"'"'s associated partition down the copy of the decision tree stored on the given processor, so each given one of said processor'"'"'s associated data objects is routed by the neural network in each of a succession of one or more non-terminal nodes to a respective child node, until the given data object is routed to a given terminal node in the processor'"'"'s copy of the tree, after which the hidden layer neural network associated with said given terminal node is used to analyze the given data object.

17. A computerized method including:

receiving a data set comprised of a plurality of data objects; and

creating a decision tree data structure having a plurality of non-terminal nodes, including a root node, and terminal nodes, wherein each of said non-terminal nodes has a plurality of child nodes, each of which is either one of said non-terminal or terminal nodes, said creating of a decision tree including;

creating for each non-terminal node a neural network, at least some of which include hidden layers;

creating for each terminal node a neural network;

supplying a plurality of said data objects to said root node as a training set; and

performing the following operation for each given non-terminal node in said tree;

using the training set data objects supplied to the given non-terminal node to train given node'"'"'s neural network; and

supplying each training set data object supplied to the given node to one of the given node'"'"'s child nodes based on the output of the given node'"'"'s neural network for the data object, once the neural net has been trained.

18. A computer system including:

means for storing a representation of a neural network capable of calculating the values of J output parameters given the value of I input parameters, where I is an integer greater than one and J is an integer greater than zero;

means for receiving a data set comprised of a plurality of data objects, said data set having N parameters, where N is an integer equal to or greater than I and where the N parameters include at least the I parameters; and

means for associating a score, from a one dimensional range of values, with each given one of said data objects as a function of the values of the one or more J parameters calculated by said neural network for the values of said given data object'"'"'s I parameters;

means for selecting a continuous range of said scores having a predetermined percent of the data objects associated with said range; and

means for selecting the set of data objects associated with said selected range.

19. A computerized method including:

receiving a data set comprised of a plurality of data objects, each of which includes a corresponding set of parameters; and

creating a decision tree data structure having a plurality of non-terminal nodes, including a root node, and terminal nodes, wherein each of said non-terminal nodes has a plurality of child nodes, each of which is either one of said non-terminal or terminal nodes, said creating of a decision tree including;

creating for each non-terminal node a neural network, having a set of input nodes, a set of one or more output nodes, and a set of weights determining which values will be produced at each output node when a given set of parameter values are supplied to the network'"'"'s input nodes;

supplying a plurality of said data objects to said root node as a training set; and

performing the following operation for each given non-terminal node in said tree;

using the training set data objects supplied to the given non-terminal node to train the given node'"'"'s neural network by applying, for each data object, to each of the neural network'"'"'s input nodes the value from a corresponding input subset of said data object'"'"'s associated parameters, and using the difference between the resulting set of values produced at the neural network'"'"'s one or more output nodes and the values of a corresponding output subset of said data object'"'"'s parameters to update the neural network'"'"'s weights so as to reduce that difference;

wherein said training includes selecting for each given non-terminal node which of the parameters associated with the data objects supplied to the given non-terminal node are to be as said output subset as a function of the data objects supplied to that node; and

supplying each data object supplied to the given node to one of the given node'"'"'s child nodes based on the output of the given node'"'"'s neural network for the data object, once the given node'"'"'s neural net has been trained.

20. A computer-implemented method for parallel processing of data, comprising:

determining from the data at least one principle axis of the data;

partitioning the data into a plurality of convex sets of data alone at least one plane orthogonal to each determined principle axis of the data corresponding to a number of processors; and

in parallel, processing the convex sets of data using a plurality of analytic models on the processors, wherein each processor receives one of the convex sets of data and uses one of the plurality of analytical models.

21. A computer system method for parallel processing of a data, comprising:

means for determining from the data at least one principle axis of the data;

means for partitioning the data into a plurality of convex sets of data along at least one plane orthogonal to each determined principle axis of the data corresponding to a number of processors; and

for processing the convex sets of data using a plurality of analytical models in parallel on the plurality of processors, wherein each processor receives one of the convex sets of data and uses of the plurality of analytical models.