Granted Patent B1

US 10,489,383 · App. 15/640,007 · Granted Nov 26, 2019

Inventor: Scott S. McCoy (Oakland, CA)

Assignee: Quantcast Corporation

G06F16/2365G06F16/24568

Abstract

Claims (97)

1. A computer-implemented method comprising:

receiving, from a data store on a server, data for a first data processing job, the received data comprising a plurality of pairings, each pairing comprising a data value and a list of data keys, the data keys having a range of possible values;

partitioning the range of possible values into a plurality of unbalanced buckets, each unbalanced bucket corresponding to a fraction of the range of possible values of the data keys, at least two unbalanced buckets of the plurality of unbalanced buckets having different corresponding fractions;

assigning each unbalanced bucket to a respective processing unit selected from a plurality of processing units;

generating an intermediate result for each unbalanced bucket by processing the data keys of each unbalanced bucket at its respective assigned processing unit;

combining the intermediate results to generate a comprehensive result;

receiving, from the data store on the server, data for a second data processing job; and

determining a sampling rate for the second data processing job by selecting an unbalanced bucket having a sampling error which does not exceed a sampling error threshold, wherein determining the sampling error comprises:

scaling the selected unbalanced bucket's intermediate result according to the selected bucket's corresponding fraction; and

comparing the scaled intermediate result to the comprehensive result.

2. The method of claim 1 , wherein receiving data for the second data processing job comprises receiving a second plurality of pairings and further comprising sampling the data keys of the second plurality of pairings according to the determined sampling rate for the second data processing job.

3. The method of claim 2 , further comprising:

estimating a result of the second data processing job by scaling a result of processing the sampled data keys.

4. The method of claim 2 , further comprising:

partitioning the sampled data keys into a plurality of sampled buckets, each sampled bucket an unbalanced bucket corresponding to a fraction of a range of possible values of the data keys, at least two sampled buckets of the plurality of sampled buckets having different corresponding fractions;

assigning each sampled bucket to a respective processing unit selected from the plurality of processing units;

generating an intermediate result for each sampled bucket;

scaling each sampled bucket's intermediate result according to the respective sampled bucket's corresponding fraction;

estimating a comprehensive result for the second data processing job by combining the scaled intermediate results of the sampled buckets;

determining a sampling rate for a third data processing job by selecting a sampled bucket having a sampling error which does not exceed the sampling error threshold and multiplying the fraction corresponding to the selected sampled bucket with the sampling rate of the second data processing job.

5. The method of claim 2 , further comprising:

determining all of the unbalanced buckets have a sampling error which exceeds the sampling error threshold;

partitioning the range of possible values into a plurality of unsampled buckets, at least one unsampled bucket from the plurality of unsampled buckets having a corresponding fraction which is larger than the largest unbalanced bucket's corresponding fraction;

assigning each unsampled bucket to a respective processing unit selected from the plurality of processing units;

generating an intermediate result for each unsampled bucket;

combining the intermediate results of processing the unsampled buckets to generate a second comprehensive result; and

determining a sampling rate for a third data processing job by selecting an unsampled bucket having a sampling error which does not exceed the sampling error threshold.

6. The method of claim 1 , wherein:

no pair of unbalanced buckets correspond to the same fraction.

7. The method of claim 1 , wherein:

at least two unbalanced buckets are matching buckets which correspond to the same fraction; and

determining the sampling rate for a second data processing job further comprises:

determining a sampling error for each of the matching buckets; and

comparing the differences between the determined sampling errors of the matching buckets to a variance threshold.

8. A non-transitory computer-readable storage medium executing computer program instructions for automatically determining a sampling rate, the computer program instructions comprising instructions for:

receiving, from a data store on a server, data for a first data processing job, the received data comprising a plurality of pairings, each pairing comprising a data value and a list of data keys, the data keys having a range of possible values;

partitioning the range of possible values into a plurality of unbalanced buckets, each unbalanced bucket corresponding to a fraction of the range of possible values of the data keys, at least two unbalanced buckets of the plurality of unbalanced buckets having different corresponding fractions;

assigning each unbalanced bucket to a respective processing unit selected from a plurality of processing units;

generating an intermediate result for each unbalanced bucket by processing the data keys of each unbalanced bucket at its respective assigned processing unit;

combining the intermediate results to generate a comprehensive result;

receiving, from the data store on the server, data for a second data processing job; and

determining the sampling rate for a second data processing job by selecting an unbalanced bucket having a sampling error which does not exceed a sampling error threshold, wherein determining the sampling error comprises:

scaling the selected unbalanced bucket's intermediate result according to the selected bucket's corresponding fraction; and

comparing the scaled intermediate result to the comprehensive result.

9. The medium of claim 8 , wherein receiving data for the second data processing job comprises receiving a second plurality of pairings and wherein the medium further comprises instructions for sampling the data keys of the second plurality of pairings according to the determined sampling rate for the second data processing job.

10. The medium of claim 9 , wherein the medium further comprises instructions for:

estimating a result of the second data processing job by scaling a result of processing the sampled data keys.

11. The medium of claim 9 , wherein the medium further comprises instructions for:

partitioning the sampled data keys into a plurality of sampled buckets, each sampled bucket an unbalanced bucket corresponding to a fraction of a range of possible values of the data keys, at least two sampled buckets of the plurality of sampled buckets having different corresponding fractions;

assigning each sampled bucket to a respective processing unit selected from the plurality of processing units;

generating an intermediate result for each sampled bucket;

scaling each sampled bucket's intermediate result according to the respective sampled bucket's corresponding fraction;

estimating a comprehensive result for the second data processing job by combining the scaled intermediate results of the sampled buckets;

determining a sampling rate for a third data processing job by selecting a sampled bucket having a sampling error which does not exceed the sampling error threshold and multiplying the fraction corresponding to the selected sampled bucket with the sampling rate of the second data processing job.

12. The medium of claim 8 , wherein:

no pair of unbalanced buckets correspond to the same fraction.

13. The medium of claim 8 , wherein:

at least two unbalanced buckets are matching buckets which correspond to the same fraction; and

determining the sampling rate for a second data processing job further comprises:

determining a sampling error for each of the matching buckets; and

comparing the differences between the determined sampling errors of the matching buckets to a variance threshold.

14. A system comprising:

a processor;

a computer-readable storage medium storing processor-executable computer program instructions for automatically determining a sampling rate, the instructions comprising instructions for:

receiving, from a data store on a server, data for a first data processing job, the received data comprising a plurality of pairings, each pairing comprising a data value and a list of data keys, the data keys having a range of possible values;

partitioning the range of possible values into a plurality of unbalanced buckets, each unbalanced bucket corresponding to a fraction of the range of possible values of the data keys, at least two unbalanced buckets of the plurality of unbalanced buckets having different corresponding fractions;

assigning each unbalanced bucket to a respective processing unit selected from a plurality of processing units;

generating an intermediate result for each unbalanced bucket by processing the data keys of each unbalanced bucket at its respective assigned processing unit;

combining the intermediate results to generate a comprehensive result;

receiving, from the data store on the server, data for a second data processing job; and

determining the sampling rate for the second data processing job by selecting an unbalanced bucket having a sampling error which does not exceed a sampling error threshold, wherein determining the sampling error comprises:

scaling the selected unbalanced bucket's intermediate result according to the selected bucket's corresponding fraction; and

comparing the scaled intermediate result to the comprehensive result.

15. The system of claim 14 , wherein receiving data for the second data processing job comprises receiving a second plurality of pairings and wherein the medium further comprises instructions for sampling the data keys of the second plurality of pairings according to the determined sampling rate for the second data processing job.

16. The system of claim 15 , wherein the medium further comprises instructions for:

estimating a result of the second data processing job by scaling a result of processing the sampled data keys.

17. The system of claim 15 , wherein the medium further comprises instructions for:

partitioning the sampled data keys into a plurality of sampled buckets, each sampled bucket an unbalanced bucket corresponding to a fraction of a range of possible values of the data keys, at least two sampled buckets of the plurality of sampled buckets having different corresponding fractions;

assigning each sampled bucket to a respective processing unit selected from the plurality of processing units;

generating an intermediate result for each sampled bucket;

scaling each sampled bucket's intermediate result according to the respective sampled bucket's corresponding fraction;

estimating a comprehensive result for the second data processing job by combining the scaled intermediate results of the sampled buckets;

determining a sampling rate for a third data processing job by selecting a sampled bucket having a sampling error which does not exceed the sampling error threshold and multiplying the fraction corresponding to the selected sampled bucket with the sampling rate of the second data processing job.

18. The system of claim 15 , wherein the medium further comprises instructions for:

determining all of the unbalanced buckets have a sampling error which exceeds the sampling error threshold;

partitioning the range of possible values into a plurality of unsampled buckets, at least one unsampled bucket from the plurality of unsampled buckets having a corresponding fraction which is larger than the largest unbalanced bucket's corresponding faction;

assigning each unsampled bucket to a respective processing unit selected from the plurality of processing units;

generating an intermediate result for each unsampled bucket;

combining the intermediate results of processing the unsampled buckets to generate a second comprehensive result; and

determining a sampling rate for a third data processing job by selecting an unsampled bucket having a sampling error which does not exceed the sampling error threshold.

19. The system of claim 14 , wherein:

no pair of unbalanced buckets correspond to the same fraction.

20. The system of claim 14 , wherein:

at least two unbalanced buckets are matching buckets which correspond to the same fraction; and

determining the sampling rate for a second data processing job further comprises:

determining a sampling error for each of the matching buckets; and

comparing the differences between the determined sampling errors of the matching buckets to a variance threshold.

Assignments (10)