Methods and apparatus to estimate cardinality through ordered statistics

Patent metadata

Field	Value
Publication number	US-12561292-B2
Application number	US-202418985592-A
Country	US
Kind code	B2
Filing date	Dec 18, 2024
Priority date	Oct 15, 2021
Publication date	Feb 24, 2026
Grant date	Feb 24, 2026

Abstract

Methods, apparatus, systems, and articles of manufacture to estimate cardinality through ordered statistics are disclosed. In an example, an apparatus includes processor circuitry to selects a sample dataset from a first reference dataset of media assets and partitions the sample dataset into m mutually exclusive subsets of approximately equal size. The processor circuitry then estimates a ratio of a sample weighted average and empirical cumulative distribution of an approximately largest order statistic from at least one of the m subsets and generates an estimate of a total cardinality of the first reference dataset by multiplying the ratio by approximately m.

First claim

The invention claimed is:

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 minimum 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 minimum 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 minimum 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 9 , wherein estimating the ratio includes determining an expected value of a logarithm of the cumulative distribution function of the base distribution.

Assignees

• Nielsen Co Us Llc

Inventors

• Sheppard Michael R

Classifications

• G06F16/24545 Primary

  Selectivity estimation or determination · CPC title

• G06F16/21 Primary

  Design, administration or maintenance of databases · CPC title