# US 2023/0069313 A1 · Method and system for estimating the cardinality of information

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0069313 A1
- Document ID: US20230069313A1
- Status: Published application
- Kind: A1
- Application number: 17/460,666
- Filed: 2021-08-30
- Published: 2023-03-02
- Earliest claimed: 2021-08-30
- Assignees: The Nielsen Company (US), LLC
- Applicants: The Nielsen Company (US), LLC
- Inventors: Michael Sheppard; Edward Murphy; Jonathan Sullivan
- Web page: https://patentgrep.com/patent/US20230069313A1

## CPC

- G06F 16/24545: {Selectivity estimation or determination}
- G06F 16/2255: {Hash tables}
- G06F 16/2358: {Change logging, detection, and notification (replication G06F16/27)}
- G06F 16/2462: {Approximate or statistical queries}
- G06F 16/951: Indexing; Web crawling techniques
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06Q 30/0246: {Traffic}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

A computer-implemented method for efficiently estimating the number of unique elements in a collection of elements comprises generating, via hash logic, hash values for each element of the collection of elements. The method further comprises specifying, in a sketch-frequency table, a set of discrete statistical values associated with the hash values and, for each discrete statistical value of the set of discrete statistical values, information indicative of a frequency at which binary representations of the hash values are associated with the discrete statistical value. The cardinality of the collection of elements is estimated based on the sketch-frequency table.

## Claims

### Claim 1

A computer-implemented method for efficiently estimating a number of unique elements in a collection of elements, the method comprising:
generating, via hash logic, hash values for each element of the collection of elements;
specifying, in a sketch-frequency table, a set of discrete statistical values associated with the hash values and, for each discrete statistical value of the set of discrete statistical values, information indicative of a frequency at which the hash values are associated with the discrete statistical value; and
estimating a cardinality of the collection of elements based on the sketch-frequency table.

### Claim 2 (depends on 1)

The computer-implemented method according to claim 1, specifying, in the sketch-frequency table, the set of discrete statistical values associated with the hash values comprises:
generating binary representations of the hash values; and
determining, for each binary representation, a discrete statistical value to correspond to a number of consecutive ones in the binary representation starting from a least significant bit, wherein the set of discrete statistical values associated with the binary representations define a geometric distribution.

### Claim 3 (depends on 1)

The computer-implemented method according to claim 1, specifying, in the sketch-frequency table, the set of discrete statistical values associated with the hash values comprises:
generating binary representations of the hash values; and
determining, for each binary representation, a discrete statistical value to correspond to a Hamming weight of the binary representation, wherein the set of discrete statistical values associated with the binary representations define a binomial distribution.

### Claim 4 (depends on 1)

The computer-implemented method according to claim 1, wherein estimating the cardinality of the collection of elements comprises iterating over the collection of elements a single time.

### Claim 5 (depends on 1)

The computer-implemented method according to claim 1, wherein estimating the cardinality of the collection of elements based on the sketch-frequency table comprises:
generating a plurality of cardinality estimates associated with a plurality of different orders of the set of discrete statistical values specified in the sketch-frequency table;
selecting, according to a Monte Carlo analysis and without replacement, at least some of the generated plurality of cardinality estimates; and
estimating the cardinality of the collection of elements as an arithmetic average of selected cardinality estimates.

### Claim 6 (depends on 1)

The computer-implemented method according to claim 1, wherein estimating the cardinality of the collection of elements based on the sketch-frequency table comprises:
initializing a running value of the cardinality to zero;
iterating over each discrete statistical value specified in sketch-frequency table;
determining, during each iteration, an update-probability indicative of a probability that future iterations will update the running value of the cardinality;
if the update-probability associated with a current iteration is different from the update-probability associated with an immediately prior iteration, adding to the running value of the cardinality a reciprocal of the update-probability associated with the immediately prior iteration.

### Claim 7 (depends on 1)

The computer-implemented method according to claim 1, wherein generating hash values for each element of the collection of elements comprises:
generating hash values that conform to a uniform distribution.

### Claim 8 (depends on 1)

The computer-implemented method according to claim 1, further comprising:
receiving a first sketch-frequency table associated with a first collection of elements;
receiving a second sketch-frequency table associated with a second collection of elements;
merging discrete statistical values specified in the first sketch-frequency table and the first sketch-frequency table into a third sketch-frequency table;
specifying respective frequencies for each discrete statistical value in the third sketch-frequency table as a sum of corresponding frequencies of discrete statistical values specified in the first sketch-frequency table and the first sketch-frequency table; and
estimating a cardinality of combined elements of the first collection of elements and the second collection of elements based on the third sketch-frequency table.

### Claim 9 (depends on 1)

The computer-implemented method according to claim 1, wherein the method is performed by a server, wherein elements of the collection of elements are associated with one or more individuals, wherein the computer-implemented method facilitates estimating a number of individuals that visited the server.

### Claim 10 (depends on 9)

The computer-implemented method according to claim 9, further comprising estimating a number of individuals that clicked on particular advertisements hosted by the server, and determining a cost-per-click associated with the particular advertisement as a function of the estimated number of individuals that clicked on the particular advertisements.

### Claim 11

A computing system:
one or more processors; and
a memory in communication with the one or more processors, wherein the memory stores instruction code that, when executed by the one or more processors, causes the computing system to perform operations comprising:
generating, via hash logic, hash values for each element of a collection of elements;
specifying, in a sketch-frequency table, a set of discrete statistical values associated with the hash values and, for each discrete statistical value of the set of discrete statistical values, information indicative of a frequency at which the hash values are associated with the discrete statistical value; and
estimating a cardinality of the collection of elements based on the sketch-frequency table.

### Claim 12 (depends on 11)

The computing system according to claim 11, specifying, in the sketch-frequency table, the set of discrete statistical values associated with the hash values comprises:
generating binary representations of the hash values; and
determining, for each binary representation, a discrete statistical value to correspond to a number of consecutive ones in the binary representation starting from a least significant bit, wherein the set of discrete statistical values associated with the binary representations define a geometric distribution.

### Claim 13 (depends on 11)

The computing system according to claim 11, specifying, in the sketch-frequency table, the set of discrete statistical values associated with the hash values comprises:
generating binary representations of the hash values; and
determining, for each binary representation, a discrete statistical value to correspond to a Hamming weight of the binary representation, wherein the set of discrete statistical values associated with the binary representations define a binomial distribution.

### Claim 14 (depends on 11)

The computing system according to claim 11, wherein estimating the cardinality of the collection of elements comprises iterating over the collection of elements a single time.

### Claim 15 (depends on 11)

The computing system according to claim 11, wherein estimating the cardinality of the collection of elements based on the sketch-frequency table comprises:
generating a plurality of cardinality estimates associated with a plurality of different orders of the set of discrete statistical values specified in the sketch-frequency table;
selecting, according to a Monte Carlo analysis and without replacement, at least some of the generated plurality of cardinality estimates; and
estimating the cardinality of the collection of elements as an arithmetic average of selected cardinality estimates.

### Claim 16 (depends on 11)

The computing system according to claim 11, wherein estimating the cardinality of the collection of elements based on the sketch-frequency table comprises:
initializing a running value of the cardinality to zero;
iterating over each discrete statistical value specified in sketch-frequency table;
determining, during each iteration, an update-probability indicative of a probability that future iterations will update the running value of the cardinality;
if the update-probability associated with a current iteration is different from the update-probability associated with an immediately prior iteration, adding to the running value of the cardinality a reciprocal of the update-probability associated with the immediately prior iteration.

### Claim 17 (depends on 11)

The computing system according to claim 11, further comprising:
receiving a first sketch-frequency table associated with a first collection of elements;
receiving a second sketch-frequency table associated with a second collection of elements;
merging discrete statistical values specified in the first sketch-frequency table and the first sketch-frequency table into a third sketch-frequency table;
specifying respective frequencies for each discrete statistical value in the third sketch-frequency table as a sum of corresponding frequencies of discrete statistical values specified in the first sketch-frequency table and the first sketch-frequency table; and
estimating a cardinality of combined elements of the first collection of elements and the second collection of elements based on the third sketch-frequency table.

### Claim 18

A non-transitory computer-readable medium having stored thereon instruction code that, when executed by one or more processors of a computing system, causes the computing system to perform operations comprising:
generating, via hash logic, hash values for each element of a collection of elements;
specifying, in a sketch-frequency table, a set of discrete statistical values associated with binary representations of the hash values and, for each discrete statistical value of the set of discrete statistical values, information indicative of a frequency at which binary representations of the hash values are associated with the discrete statistical value; and
estimating a cardinality of the collection of elements based on the sketch-frequency table.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium according to claim 18, wherein estimating the cardinality of the collection of elements based on the sketch-frequency table comprises:
generating a plurality of cardinality estimates associated with a plurality of different orders of the set of discrete statistical values specified in the sketch-frequency table;
selecting, according to a Monte Carlo analysis and without replacement, at least some of the generated plurality of cardinality estimates; and
estimating the cardinality of the collection of elements as an arithmetic average of selected cardinality estimates.

### Claim 20 (depends on 18)

The non-transitory computer-readable medium according to claim 18, wherein estimating the cardinality of the collection of elements based on the sketch-frequency table comprises:
initializing a running value of the cardinality to zero;
iterating over each discrete statistical value specified in sketch-frequency table;
determining, during each iteration, an update-probability indicative of a probability that future iterations will update the running value of the cardinality;
if the update-probability associated with a current iteration is different from the update-probability associated with an immediately prior iteration, adding to the running value of the cardinality a reciprocal of the update-probability associated with the immediately prior iteration.
