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

Patent metadata

Field	Value
Publication number	US-12554696-B2
Application number	US-202418761748-A
Country	US
Kind code	B2
Filing date	Jul 2, 2024
Priority date	Jun 30, 2020
Publication date	Feb 17, 2026
Grant date	Feb 17, 2026

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

The invention 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 generated using first noise arrays, wherein the first Bloom filter array is representative of unique media impressions of a media item logged by a first party; obtaining a second Bloom filter array generated using second noise arrays, wherein the second Bloom filter array is representative of unique media impressions of the media item logged by a second party; 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 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 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 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.

5 . 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.

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

7 . A method comprising:
obtaining, by a computing system, a first Bloom filter array generated using first noise arrays, wherein the first Bloom filter array is representative of unique media impressions of a media item logged by a first party; obtaining, by the computing system, a second Bloom filter array generated using second noise arrays, wherein the second Bloom filter array is representative of unique media impressions of the media item logged by a second party; 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 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 information that is derived from the cardinality.

8 . The method of claim 7 , 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.

9 . The method of claim 8 , 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.

10 . The method of claim 7 , 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.

11 . The method of claim 7 , 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.

12 . The method of claim 7 , further comprising obtaining the first noise arrays.

13 . 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 generated using first noise arrays, wherein the first Bloom filter array is representative of unique media impressions of a media item logged by a first party; obtaining a second Bloom filter array generated using second noise arrays, wherein the second Bloom filter array is representative of unique media impressions of the media item logged by a second party; 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 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 information that is derived from the cardinality.

14 . The non-transitory computer-readable medium of claim 13 , 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.

15 . The non-transitory computer-readable medium of claim 14 , 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.

16 . The non-transitory computer-readable medium of claim 13 , 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.

17 . The non-transitory computer-readable medium of claim 13 , 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

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