US6889221B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel random sampling
Assignee: Teradata US Inc
•
Filing: 2001-08-23
•
Granted: 2005-05-03
•
Expires: 2021-08-23
Abstract
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.
Inventors
- 👤 Gang Luo
- 👤 Ambuj Shatdal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 21:22
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2462; G06F16/2453; G06F16/24532; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99935; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
44 words
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.
Claim 2
Independent Claim
44 words
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.
Claim 3
Dependent Claim
29 words
The method of claim 1 , wherein providing the random number generators in the plural nodes comprises providing random number generators in at least some of the plural nodes.
Claim 4
Independent Claim
52 words
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.
Claim 5
Independent Claim
52 words
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.
Claim 6
Dependent Claim
28 words
The method of claim 1 , further comprising determining a number of random samples to select in each node based on the generated random numbers in the node.
Claim 7
Dependent Claim
38 words
The method of claim 1 , further comprising: providing a plurality of parameters; adjusting values of the parameters based on values of the random numbers; and determining a number of random samples to select based on the parameters.
Claim 8
Dependent Claim
31 words
The method of claim 5 , wherein providing the parameters, adjusting the values of the parameters, and determining the number of random samples are performed in each of the plural nodes.
Claim 9
Dependent Claim
41 words
The method of claim 5 , further comprising: associating the parameters with corresponding predefined ranges; determining which range each random number falls within; and adjusting the value of one of the parameters based on the determined range of each random number.
Claim 10
Dependent Claim
22 words
The method of claim 7 , wherein adjusting the value of the one parameter comprises incrementing the value of the one parameter.
Claim 11
Dependent Claim
28 words
The method of claim 8 , wherein incrementing the value of the one parameter occurs in response to each occurrence of a random number in the determined range.
Claim 12
Dependent Claim
28 words
The method of claim 7 , further comprising communicating certain of the parameters between nodes, each node determining the number of random samples based on the communicated parameters.
Claim 13
Dependent Claim
26 words
The method of claim 1 , further comprising: defining plural ranges; and counting a number of occurrences of random numbers in each of the plural ranges.
Claim 14
Dependent Claim
26 words
The method of claim 11 , further comprising: storing plural parameters having values set to represent the number of occurrences of random numbers in corresponding ranges.
Claim 15
Dependent Claim
41 words
The method of claim 1 , further coring: generating random number seeds at one node; sending the random member seeds to plural nodes from the one node; and the random number generators in the plural nodes using corresponding random number seeds.
Claim 16
Dependent Claim
55 words
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.
Claim 17
Dependent Claim
55 words
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.
Claim 18
Dependent Claim
26 words
The database system of claim 14 , wherein each node further comprises a processor, and wherein the controller is a software program executable by the processor.
Claim 19
Dependent Claim
53 words
The database system of claim 14 , wherein one of the nodes comprises a first random number generator, and wherein each of the nodes comprises a second random number generator to generate the random numbers, the first random number generator to generate random number seeds for use by the second random number generators.
Claim 20
Dependent Claim
19 words
The database system of claim 16 , wherein the one node communicates the random number seeds to corresponding nodes.
Claim 21
Dependent Claim
50 words
The database system of claim 16 , wherein the plural nodes comprise nodes i, i=1−L, wherein the first random number generator is adapted to generate random number seeds s i , i=1L, and wherein the one node is adapted to send each random number seed s i to node i.
Claim 22
Dependent Claim
46 words
The database system of claim 18 , wherein the second random number generator in each node i is adapted to generate random numbers r 1 . . . r Mi , where M i represents a number of random numbers to be generated in node i.
Claim 23
Dependent Claim
58 words
The database system of claim 19 , the storage in each node i to store array elements A i1 . . . A iL , the controller adapted to adjust the value of A ij , j equal to a value between 1 and L, based on which of plural predefined ranges each random number r fills within.
Claim 24
Dependent Claim
22 words
The database system of claim 20 , wherein each node is adapted to communicate certain of these array elements to other nodes.
Claim 25
Dependent Claim
31 words
The database system of claim 21 , wherein the controller in each node is adapted to sum values of the array elements to derive the number of random samples to generate.
Claim 26
Dependent Claim
47 words
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.
Claim 27
Dependent Claim
47 words
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.
Claim 28
Dependent Claim
30 words
The article of claim 23 , wherein the instructions when executed cause the database system to provide a first random number generator in each node to generate the random numbers.
Claim 29
Dependent Claim
40 words
The article of claim 24 , wherein the instructions when executed cause the database system to provide a second random number generator in one of the nodes to generate random number seeds for use by the first random number generators.
Claim 30
Dependent Claim
25 words
The article of claim 25 , wherein the instructions when executed cause the database system to distribute the random number seeds to the plural nodes.
Claim 31
Dependent Claim
48 words
The article of claim 23 , wherein the instructions when executed cause the database system to further: define parameters in each node; and adjust the parameters based on values of the random numbers in each node, wherein determining the number of random samples is based on the parameters.
Claim 32
Dependent Claim
29 words
The article of claim 27 , wherein the instructions when executed cause the database system to distribute certain of the parameters from each of the nodes to other nodes.
Claim 33
Dependent Claim
31 words
The article of claim 28 , wherein the instructions when executed cause the database system to sum the parameters at each of the nodes to derive the number of random samples.
Claim 34
Dependent Claim
55 words
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.
Claim 35
Dependent Claim
55 words
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.
Claim 36
Dependent Claim
33 words
The article of claim 30 , wherein the instructions when executed cause the database system to determine a number of random samples to generate in each node based on the generated random number.
References Cited (Backward Citations)
US5878426A
Cited
US6226629B1
Cited
US6003036A
Cited
US6223171B1
Cited
US20020198863A1
Cited
US6564221B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-05-02 | 2008-11-01 | 2009-05-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-05-02 | 2012-11-01 | 2013-05-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-05-02 | 2016-11-01 | 2017-05-03 | $7700.00 | Window Closed / Lapsed |