Methods and apparatus to estimate cardinality across multiple datasets represented using bloom filter arrays

Patent metadata

Field	Value
Publication number	US-11854030-B2
Application number	US-202117362404-A
Country	US
Kind code	B2
Filing date	Jun 29, 2021
Priority date	Jun 29, 2021
Publication date	Dec 26, 2023
Grant date	Dec 26, 2023

Abstract

Methods and apparatus to estimate cardinality across multiple datasets represented using Bloom filter arrays are disclosed. Disclosed examples include processor circuitry to execute and/or instantiate instructions to determine an inclusion-exclusion expression that defines an audience size for a user group of interest. Terms in the inclusion-exclusion expression corresponding to either a first cardinality of a first one of at least three Bloom filter arrays or a second cardinality of a union of two or more of the Bloom filter arrays. Different ones of the Bloom filter arrays representative of different sets of users who accessed media. The at least one processor further to estimate, based on the inclusion-exclusion expression, the audience size of the user group of interest.

First claim

What is claimed is:

1. An apparatus comprising:
communications interface circuitry to:
transmit, via first network communications, bloom filter parameters to a first database proprietor, a second database proprietor, and a third database proprietor;
receive, via second network communications, first, second, and third Bloom filter arrays generated by respective first, second, and third servers of respective ones of the first, second, and third database proprietors, each of the first, second, and third Bloom filter arrays having a length, the length defined by the bloom filter parameters, different ones of the first, second, and third Bloom filter arrays representative of different sets of users registered with respective ones of the first, second, and third database proprietors and that accessed media, the first, second, and third Bloom filter arrays including differential privacy noise, the first, second, and third Bloom filter arrays generated to maintain a privacy of the different sets of users such that duplication of the users across the different sets of users cannot be directly determined from the Bloom filter array to determine of an audience size across the different sets of users;

at least one memory;
instructions; and
programmable circuitry to execute and/or instantiate the instructions to:
determine, by executing a numerical solver, the length defined by the Bloom filter parameters provided to the first, second, and third database proprietors, the length determined to correspond to a minimum length to provide a first relative error in an estimate of the audience size no greater than a second relative error at a confidence level;
determine an inclusion-exclusion expression that defines the audience size for a user group of interest, terms in the inclusion-exclusion expression corresponding to either a first cardinality of the first Bloom filter array or a second cardinality of a union of two or more of the first, second, and third Bloom filter arrays;
estimate, based on the inclusion-exclusion expression, the audience size of the user group of interest that accounts for the duplication of the users across the different sets of users, the length determined to reduce at least one of memory requirements to store data associated with processing of the first, second, and third Bloom filter arrays or processing requirements to implement the estimation relative to a longer length for the first, second, and third Bloom filter arrays; and
cause the communications interface circuitry to transmit, via a third network communication, a report based on the estimate of the audience size to a third-party entity.

2. The apparatus of claim 1 , wherein the programmable circuitry is to:
determine an argument for a logarithm based on the inclusion-exclusion expression; and
estimate the audience size based on the logarithm.

3. The apparatus of claim 2 , wherein the argument includes at least one of (i) a first ratio of a first count of array elements with a particular value in the first Bloom filter array to the length of the first, second, and third Bloom filter arrays or (ii) a second ratio of a second count of array elements with the particular value in a bitwise union of two or more of the first, second, and third Bloom filter arrays.

4. The apparatus of claim 3 , wherein the particular value is 0.

5. The apparatus of claim 3 , wherein the argument includes the first ratio or the second ratio when the corresponding terms in the inclusion-exclusion expression are added, and the argument includes an inverse of the first ratio or an inverse of the second ratio when the corresponding terms in the inclusion-exclusion expression are subtracted.

6. The apparatus of claim 3 , wherein the first ratio and the second ratio include respective exponents corresponding to respective constant coefficients in front of the corresponding terms in the inclusion-exclusion expression.

7. The apparatus of claim 1 , wherein the programmable circuitry is to identify a subset of mutually exclusive disjoint datasets associated with the different sets of users, the subset corresponding to the user group of interest, the inclusion-exclusion expression identified based on the subset.

8. The apparatus of claim 7 , wherein the subset corresponds to all of the mutually exclusive disjoint datasets, all of the mutually exclusive disjoint datasets corresponding to a union of all the different sets of users.

9. The apparatus of claim 7 , wherein the subset corresponds to less than a union of all the different sets of users.

10. The apparatus of claim 1 , wherein the communications interface circuitry is to receive one or more additional Bloom filter arrays, and the programmable circuitry is to estimate the audience size based on the one or more additional Bloom filter arrays.

11. An apparatus comprising:
communications interface circuitry to:
transmit, via first network communications, bloom filter parameters to a first database proprietor, a second database proprietor, and a third database proprietor;
receive, via second network communications, first, second, and third Bloom filter arrays generated by respective first, second, and third servers of respective ones of the first, second, and third database proprietors, each of the first, second, and third Bloom filter arrays having a length, the length defined by the bloom filter parameters, different ones of the first, second, and third Bloom filter arrays representative of different sets of users registered with respective ones of the first, second, and third database proprietors and corresponding to media accesses, the first, second, and third Bloom filter arrays including differential privacy noise, the first, second, and third Bloom filter arrays generated to maintain a privacy of the different sets of users such that duplication of the users across the different sets of users cannot be directly determined from the Bloom filter arrays to determine an audience size across the different sets of users:

at least one memory; and
programmable circuitry including one or more of:
at least one of a central processing unit, a graphic processing unit, or a digital signal processor, the at least one of the central processing unit, the graphic processing unit, or the digital signal processor having control circuitry to control data movement within the processor circuitry, arithmetic and logic circuitry to perform one or more first operations corresponding to instructions, and one or more registers to store a result of the one or more first operations, the instructions in the apparatus;
a Field Programmable Gate Array (FPGA), the FPGA including first logic gate circuitry, a plurality of configurable interconnections, and storage circuitry, the first logic gate circuitry and the interconnections to perform one or more second operations corresponding to the instructions, the storage circuitry to store a result of the one or more second operations; or
Application Specific Integrate Circuitry (ASIC) including second logic gate circuitry to perform one or more third operations corresponding to the instructions;

the programmable circuitry to perform at least one of the first operations, the second operations or the third operations to instantiate:
Bloom filter parameter analysis circuitry to determine, by implementing a numerical solver, the defined by the Bloom filter parameters provided to the first, second, and third database proprietors, the length determined to correspond to a minimum length to provide a first relative error in an estimate of the audience size no greater than a second relative error at a confidence level;
expression generation circuitry to determine an inclusion-exclusi

Assignees

• Nielsen Co Us Llc

Inventors

• Sheppard Michael
• Sullivan Jonathan
• Morovati Lopez Diane
• Dailey Jake Ryan
• Summers Christie Nicole
• Poppie Molly

Classifications

• G06Q30/0204 Primary

  Market segmentation · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06Q30/0201 Primary

  Market modelling; Market analysis; Collecting market data · CPC title