Methods and apparatus to estimate cardinality through ordered statistics

1. A computing system comprising a processor, the computing system configured to perform a set of acts comprising:

selecting a sample dataset from a reference dataset of media assets;

partitioning the sample dataset into m mutually exclusive subsets of samples of approximately equal size, wherein m is an integer greater than three, and wherein partitioning the sample dataset comprises populating a first set of memory locations in a memory with a first subset of samples of the m subsets of samples and assigning a first register to be a working storage location for a value representing the first subset;

estimating a ratio of a sample weighted average and empirical cumulative distribution of a largest order statistic from at least one of the m subsets; and

generating an estimate of a total cardinality of the reference dataset by multiplying the ratio by m.

2. The computing system of claim 1 , wherein samples in the sample dataset are independently distributed among the reference dataset.

3. The computing system of claim 1 , wherein a base distribution of the reference dataset includes a cumulative distribution function.

4. The computing system of claim 3 , wherein estimating the ratio includes determining an expected value of a logarithm of the cumulative distribution function of the base distribution.

5. A non-transitory machine readable storage medium comprising instructions that, when executed, cause a computing system to at least:

select a sample dataset from a reference dataset of media assets;

partition the sample dataset into m mutually exclusive subsets of samples of approximately equal size, wherein m is an integer greater than three, and wherein partitioning the sample dataset comprises populating a first set of memory locations in a memory with a first subset of samples of the m subsets of samples and assigning a first register to be a working storage location for a value representing the first subset;

estimate a ratio of a sample weighted average and empirical cumulative distribution of a largest order statistic from at least one of the m subsets; and

generate an estimate of a total cardinality of the reference dataset by multiplying the ratio by m.

6. The non-transitory machine readable storage medium of claim 5 , wherein samples in the sample dataset are independent and identically distributed among the reference dataset.

7. The non-transitory machine readable storage medium of claim 5 , wherein a base distribution of the reference dataset includes a cumulative distribution function.

8. The non-transitory machine readable storage medium of claim 7 , wherein to estimate the ratio includes to take an expected value of a logarithm of the cumulative distribution function of the base distribution.

9. A method comprising:

selecting a sample dataset from a reference dataset of media assets;

partitioning the sample dataset into m mutually exclusive subsets of samples of approximately equal size, wherein m is an integer greater than three, and wherein partitioning the sample dataset comprises populating, by a computing system, a first set of memory locations in a memory with a first subset of samples of the m subsets of samples and assigning a first register to be a working storage location for a value representing the first subset;

estimating a ratio of a sample weighted average and empirical cumulative distribution of a largest order statistic from at least one of the m subsets; and

generating an estimate of a total cardinality of the reference dataset by multiplying the ratio by m.

10. The method of claim 9 , wherein samples in the sample dataset are independently distributed among the reference dataset.

11. The method of claim 9 , wherein a base distribution of the reference dataset includes a cumulative distribution function.

12. The method of claim 11 , wherein estimating the ratio includes determining an expected value of a logarithm of the cumulative distribution function of the base distribution.