Approximate metric for dataset using representative subset
Techniques for processing a large dataset to extract information from the dataset, where the processing is performed by multiple systems and where the entire dataset, due to its size, cannot be loaded into the memory of any one of the multiple systems. In certain implementations, the information extracted from the dataset is in the form of a set of one or more statistical metrics computed for the dataset. For example, the dataset may include datapoints related to a machine-learning (ML) model, and a metric value can be computed for the ML model based upon the dataset datapoints. The metric value may, for example, be a metric that measures the performance of the ML model.
1. A computer-implemented method performed by a plurality of data processing systems, the method comprising:
for an input dataset for which a metric is to be computed, partitioning the input dataset into a plurality of non-overlapping partitions, each partition in the plurality of non-overlapping partitions comprising a plurality of data points from the input dataset, wherein, for each data processing system in the plurality of data processing systems, a size of the input dataset is larger than a system memory associated with the data processing system;
for each partition in the plurality of non-overlapping partitions, identifying a representative subset for the partition, wherein the representative subset for a partition comprises a subset of data points selected from the plurality of data points in the partition;
iteratively merging the representative subsets identified for the plurality of non-overlapping partitions until there is a single subset;
computing a value for the metric using the data points in the single subset; and
outputting the value.
2. The computer-implemented method of claim 1 , wherein each partition of the plurality of non-overlapping partitions is transmitted to a different data-processing system of the plurality of data-processing systems.
3. The computer-implemented method of claim 1 , wherein the representative subset approximates the data points included in the partition, wherein the representative subset is included in a set of representative subsets, and wherein the set of representative subsets corresponds to the set of non-overlapping partitions.
4. The computer-implemented method of claim 1 , wherein the computed value is an approximate value for the metric for the input dataset.
5. The computer-implemented method of claim 1 , wherein identifying a representative subset for each partition in the plurality of partitions comprises:
performing processing by a first data processing system from the plurality of data processing system, wherein the performing processing by the first data processing system comprises:
receiving, by the first data processing system, a first partition of the plurality of non-overlapping partitions;
selecting, by the first data processing system, a first representative subset of datapoints from the datapoints in the first partition;
performing processing by a second data processing system from the plurality of data processing system, wherein the performing processing by the second data processing system comprises:
receiving, by the second data processing system, a second partition of the plurality of non-overlapping partitions; and
selecting, by the second data processing system, a second representative subset of datapoints from the datapoints in the second partition, wherein the processing performed by the first data processing system is performed concurrently with the processing performed by the second data processing system.
6. The computer-implemented method of claim 5 , further comprising: merging the first representative subset and the second representative subset to identify a third representative subset, wherein merging the first representative subset and the second representative subset comprises identifying, from the first representative subset of datapoints and the second representative subset of datapoints, a third representative subset of datapoints, wherein a datapoint in the third representative subset of datapoints is in the first representative subset of datapoints or in the second representative subset of datapoints, and wherein merging the first representative subset and the second representative subset to identify the third representative subset is performed by a third data processing system from the plurality of data processing systems.
7. The computer-implemented method of claim 6 , wherein:
the first representative subset is representative of a first partition or of a first merged dataset of previously merged representative subsets; and
the second representative subset is representative of a second partition or of a second merged dataset of previously merged representative subsets.
8. The computer-implemented method of claim 1 , wherein the input dataset includes datapoints related to a machine-learning model, and wherein the metric is a metric associated with the machine-learning model.
9. The computer-implemented method of claim 8 , wherein the metric measures a performance of the machine-learning model, and wherein the metric is an accuracy metric, a precision metric, or a recall metric.
10. The computer-implemented method of claim 9 , further comprising determining whether to train the machine-learning model based upon the value computed for the metric.
11. The computer-implemented method of claim 1 , further comprising receiving the input dataset as a stream.
12. A system comprising:
a plurality of data processing systems including a first data processing system, a second data processing system, and a third data processing system, wherein:
the first data processing system is configured to perform processing comprising:
receiving an input dataset for which a metric is to be computed;
partitioning the input dataset into a plurality of non-overlapping partitions, each partition in the plurality of non-overlapping partitions comprising a plurality of data points from the input dataset, the plurality of partitions including a first partition and a second partition;
communicating the first partition to the second data processing system; and
communicating the second partition to the third data processing system;
the second data processing system is configured to perform processing comprising selecting a subset of datapoints from datapoints in the first partition to form a first subset that is representative of the datapoints in the first partition;
the third data processing system is configured to perform processing comprising selecting a subset of datapoints from datapoints in the second partition to form a second subset that is representative of the datapoints in the second partition; and
at least one data processing system from the plurality of data processing system is configured to perform processing comprising:
receiving a final subset that is selected based upon a plurality of subsets selected for the plurality of partitions, the plurality of subsets including the first subset and the second subset;
computing a value for the metric using the datapoints in the final subset; and
outputting the computed value.
13. The system of claim 12 , wherein:
the plurality of data processing systems further comprises a fourth data processing system; and
the fourth data processing system is configured to perform processing comprising:
receiving the first subset from the second data processing system;
receiving the second subset from the third data processing system;
merging datapoints in the first subset with datapoints in the second subset to form a merged subset; and
selecting a third subset that includes a subset of datapoints from the merged subset.
14. The system of claim 12 , wherein the input dataset includes datapoints related to a machine-learning model, and wherein the metric is a metric associated with the machine-learning model.
15. The system of claim 14 , wherein the metric represents a performance of the machine-learning model, and wherein the metric is an accuracy metric, a precision metric, or a recall metric.
16. The system of claim 12 , wherein receiving the input dataset comprises receiving the input dataset as a stream.
17. A non-transitory computer-readable memory storing a plurality of instructions executable by one or more processors, the plurality of instructions comprising instructions that when executed by the one or more processors cause the one or more processors to perform operations comprising:
for an input dataset comprising a plurality of data points, partitioning the input dataset into a plurality of non-overlapping partitions, each partition in the plurality of non-overlapping partitions comprising a plurality of data points from the input dataset;
for each partition in the plurality of non-overlapping partitions, identifying a representative subset for the partition, wherein the representative subset for a partition comprises a subset of data points selected from the plurality of data points in the partition;
iteratively merging the representative subsets identified for the plurality of non-overlapping partitions until there is a single subset;
computing a metric value using the data points in the single subset; and
outputting the metric value to a consumer of the metric value.
18. The non-transitory computer-readable memory of claim 17 , wherein each partition of the plurality of non-overlapping partitions is transmittable to a different data-processing system of a set of data-processing systems, and wherein each partition of the set of non-overlapping partitions comprises a volume of data for which a corresponding data-processing system of the set of data-processing systems is configured to load all at the same time.
19. The non-transitory computer-readable memory of claim 17 , wherein the representative subset is configured to approximate the data points included in the partition, and wherein the representative subset is included in a set of representative subsets corresponding to the set of non-overlapping partitions.
20. The non-transitory computer-readable memory of claim 17 , wherein the input dataset includes datapoints related to a machine-learning model, wherein the metric is a metric associated with the machine-learning model, and wherein the input dataset is receivable as a stream.