Methods and apparatus to estimate cardinality of users represented across multiple bloom filter arrays

Patent metadata

Field	Value
Publication number	US-12038898-B2
Application number	US-202318364535-A
Country	US
Kind code	B2
Filing date	Aug 3, 2023
Priority date	Jun 30, 2020
Publication date	Jul 16, 2024
Grant date	Jul 16, 2024

Abstract

Methods and apparatus to estimate cardinality of users represented across multiple bloom filter arrays are disclosed. Examples includes processor circuitry to execute and/or instantiate instructions to generate a first composite Bloom filter array based on first and second Bloom filter arrays. The processor circuitry is to generate a final composite Bloom filter array based on the first composite Bloom filter array and a third Bloom filter array. Different ones of the first, second, and third Bloom filter arrays representative of different sets of users who accessed media. The first, second, and third Bloom filter arrays including differential privacy noise. The processor circuitry to estimate a cardinality of a union of the first, second, and third Bloom filter arrays based on the final composite Bloom filter array.

First claim

What is claimed is:

1. A computing system comprising a processor and a memory, the computing system configured to perform a set of acts comprising:
obtaining a first Bloom filter array via a first network communication from a first party, the first Bloom filter array generated using first noise arrays;
obtaining a second Bloom filter array, the second Bloom filter array generated using second noise arrays;
generating an initial composite Bloom filter array based on the first Bloom filter array and the second Bloom filter array;
estimating effective noise arrays for the initial composite Bloom filter array based on the first noise arrays and the second noise arrays;
obtaining a third Bloom filter array, the third Bloom filter array generated using third noise arrays;
generating a final composite Bloom filter array based on the initial composite Bloom filter array and the third Bloom filter array;
estimating a cardinality of the final composite Bloom filter array based on the effective noise arrays and the third noise arrays; and
transmitting, to another computing system, a report conveying audience measurement information that is derived from the cardinality.

2. The computing system of claim 1 , wherein generating the initial composite Bloom filter array comprises determining a bit-wise union of the first Bloom filter array and the second Bloom filter array.

3. The computing system of claim 2 , wherein generating the final composite Bloom filter array comprises determining a bit-wise union of the initial composite Bloom filter array and the third Bloom filter array.

4. The computing system of claim 1 , wherein:
the first Bloom filter array is representative of unique media impressions logged by the first party,
the second Bloom filter array is representative of unique media impressions logged by a second party,
the unique media impressions logged by the first party and the unique media impressions logged by the second party correspond to a same media item.

5. The computing system of claim 1 , wherein:
the first noise arrays define probabilities for bit-flipping values in individual elements of the first Bloom filter array, and
the second noise arrays define probabilities for bit-flipping values in individual elements of the second Bloom filter array.

6. The computing system of claim 1 , wherein the effective noise arrays define probabilities for bit-flipping values in individual elements of a latent Bloom filter array that would result in the initial composite Bloom filter array, the latent Bloom filter array corresponding to a bit-wise union of a first private array from which the first Bloom filter array is generated and a second private array from which the second Bloom filter array is generated.

7. The computing system of claim 1 , wherein the set of acts further comprises obtaining the first noise arrays from the first party.

8. A method comprising:
obtaining, by a computing system, a first Bloom filter array via a first network communication from a first party, the first Bloom filter array generated using first noise arrays;
obtaining, by the computing system, a second Bloom filter array, the second Bloom filter array generated using second noise arrays;
generating, by the computing system, an initial composite Bloom filter array based on the first Bloom filter array and the second Bloom filter array;
estimating, by the computing system, effective noise arrays for the initial composite Bloom filter array based on the first noise arrays and the second noise arrays;
obtaining, by the computing system, a third Bloom filter array, the third Bloom filter array generated using third noise arrays;
generating, by the computing system, a final composite Bloom filter array based on the initial composite Bloom filter array and the third Bloom filter array;
estimating, by the computing system, a cardinality of the final composite Bloom filter array based on the effective noise arrays and the third noise arrays; and
transmitting, by the computing system to another computing system, a report conveying audience measurement information that is derived from the cardinality.

9. The method of claim 8 , wherein generating the initial composite Bloom filter array comprises determining a bit-wise union of the first Bloom filter array and the second Bloom filter array.

10. The method of claim 9 , wherein generating the final composite Bloom filter array comprises determining a bit-wise union of the initial composite Bloom filter array and the third Bloom filter array.

11. The method of claim 8 , wherein:
the first Bloom filter array is representative of unique media impressions logged by the first party,
the second Bloom filter array is representative of unique media impressions logged by a second party,
the unique media impressions logged by the first party and the unique media impressions logged by the second party correspond to a same media item.

12. The method of claim 8 , wherein:
the first noise arrays define probabilities for bit-flipping values in individual elements of the first Bloom filter array, and
the second noise arrays define probabilities for bit-flipping values in individual elements of the second Bloom filter array.

13. The method of claim 8 , wherein the effective noise arrays define probabilities for bit-flipping values in individual elements of a latent Bloom filter array that would result in the initial composite Bloom filter array, the latent Bloom filter array corresponding to a bit-wise union of a first private array from which the first Bloom filter array is generated and a second private array from which the second Bloom filter array is generated.

14. The method of claim 8 , further comprising obtaining the first noise arrays from the first party.

15. A non-transitory computer-readable medium having stored therein instructions that when executed by a computing system cause the computing system to perform a set of acts comprising:
obtaining a first Bloom filter array via a first network communication from a first party, the first Bloom filter array generated using first noise arrays;
obtaining a second Bloom filter array, the second Bloom filter array generated using second noise arrays;
generating an initial composite Bloom filter array based on the first Bloom filter array and the second Bloom filter array;
estimating effective noise arrays for the initial composite Bloom filter array based on the first noise arrays and the second noise arrays;
obtaining a third Bloom filter array, the third Bloom filter array generated using third noise arrays;
generating a final composite Bloom filter array based on the initial composite Bloom filter array and the third Bloom filter array;
estimating a cardinality of the final composite Bloom filter array based on the effective noise arrays and the third noise arrays; and
transmitting, to another computing system, a report conveying audience measurement information that is derived from the cardinality.

16. The non-transitory computer-readable medium of claim 15 , wherein generating the initial composite Bloom filter array comprises determining a bit-wise union of the first Bloom filter array and the second Bloom filter array.

17. The non-transitory computer-readable medium of claim 16 , wherein generating the final composite Bloom filter array comprises determining a bit-wise union of the initial composite Bloom filter array and the third Bloom filter array.

18. The non-transitory computer-readable medium of claim 15 , wherein:
the first Bloom filter array is repres

Assignees

• Nielsen Co Us Llc

Inventors

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

Classifications

• G06F16/2456

  Join operations · CPC title

• G06F15/80

  comprising an array of processing units with common control, e.g. single instruction multiple data processors (G06F15/82 takes precedence {; for correlation function computation G06F17/15}) · CPC title

• G06F2015/763

  ASIC · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F15/7867

  with reconfigurable architecture · CPC title