Parallel random sampling
AssigneeNCR Corporation
InventorsGang Luo, Ambuj Shatdal
Life of this patent
Estimating the term…
Abstract
A parallel random sampling algorithm (such as a parallel simple random sampling algorithm) utilizes the parallelism of a parallel relational database management system. A random number generator in one node generates random number seeds for a second random number generator in each of the nodes. Random numbers generated by the second random number generators in parallel are used to obtain random sample tuples in each of the nodes.
Claims31
A method for use in a parallel database system having plural nodes, comprising:
- providing random number generators in the plural nodes;
- generating, in parallel random numbers using the random number generators in the plural nodes;
- and
- performing random sampling using the generated random numbers.
The method of clam 1, wherein the random number generators in the plural nodes are part of a first set of random number generators, the method further comprising using at least one other random number generator to generate random numbers provided as seeds to the first set of random number generators.
A database system comprising:
- a plurality of nodes, wherein each of at least two of the plurality of nodes comprises:
- a storage for storing tuples of a relation;
- and
- a controller adapted to generate random numbers;
- the controller adapted to determine a number of random samples to generate in the node using the random numbers.
An article comprising at least one storage medium storing instructions that when executed cause a database system to:
- generate random numbers in each of plural nodes of the database system;
- and
- use the random numbers to determine a number of random samples to generate in each node.
An article comprising at least one storage medium storing instructions executable in a database system having plural nodes, the instructions when executed causing a system to:
- generate random number seeds;
- communicate the random number seeds to the plural nodes;
- and
- generate random numbers in each node using at least one of the random number seeds.
Dependencies are inferred from the claim text.