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

Patent metadata

Field	Value
Publication number	US-11741068-B2
Application number	US-202117362419-A
Country	US
Kind code	B2
Filing date	Jun 29, 2021
Priority date	Jun 30, 2020
Publication date	Aug 29, 2023
Grant date	Aug 29, 2023

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. An apparatus comprising:
communication circuitry to:
receive a first Bloom filter array via a first network communication from a first server of a first database proprietor;
receive a second Bloom filter array via a second network communication from a second server of a second database proprietor; and
receive a third Bloom filter array from at least one of the first server, the second server, or a third server of a third database proprietor;

at least one memory;
instructions in the apparatus; and
programmable circuitry to execute and/or instantiate the instructions to:
generate a first composite Bloom filter array based on the first and second Bloom filter arrays;
generate noise arrays for the first composite Bloom filter array, the noise arrays distinct from the first Bloom filter array, distinct from the second Bloom filter array, and distinct from the first composite Bloom filter array;
generate a final composite Bloom filter array based on the first composite Bloom filter array, the noise arrays, and the third Bloom filter array, different ones of the first, second, and third Bloom filter arrays representative of different sets of users who registered with respective ones of the first, second, and third database proprietors and who 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 an overlap between the different sets of users cannot be directly determined to enable determination of an audience size across the different sets of users;
estimate a cardinality of a union of the first, second, and third Bloom filter arrays based on the final composite Bloom filter array; and
cause the communication circuitry to transmit, via a third network communication, a report based on the cardinality to a third-party entity.

2. The apparatus of claim 1 , wherein the programmable circuitry is to:
generate the first composite Bloom filter array based on a bit-wise union of the first and second Bloom filter arrays; and
generate the final composite Bloom filter array based on a bit-wise union of the first composite Bloom filter array and the third Bloom filter array.

3. The apparatus of claim 1 , wherein the noise arrays define probabilities for bit-flipping values in individual elements of a latent Bloom filter array that would result in the first composite Bloom filter array, the latent Bloom filter array corresponding to a bit-wise union of the first and second Bloom filter arrays prior to addition of the differential privacy noise.

4. The apparatus of claim 1 , wherein the programmable circuitry is to:
generate a binary tree having leaf nodes and non-leaf nodes, different ones of the leaf nodes to be associated with different ones of public Bloom filter arrays provided by corresponding database proprietors, the public Bloom filter arrays including the first, second, and third Bloom filter arrays, the corresponding database proprietors including at least two of the first, second, or third database proprietors, different ones of the non-leaf nodes to be associated with different ones of composite Bloom filter arrays, the different ones of the composite Bloom filter arrays including the first composite Bloom filter array and the final composite Bloom filter array; and
generate the different ones of the composite Bloom filter arrays according to a topology of the binary tree.

5. The apparatus of claim 1 , wherein a number of the users is in at least the hundreds of thousands, and the first, second, and third Bloom filter arrays are hundreds of elements in length.

6. The apparatus of claim 3 , wherein the programmable circuitry is to generate the noise arrays based on first and second pairs of noise probability arrays associated with respective ones of the first and second Bloom filter arrays.

7. The apparatus of claim 4 , wherein the programmable circuitry is to dynamically construct the topology of the binary tree for successive ones of the composite Bloom filter arrays to be generated based on previously generated ones of the composite Bloom filter arrays.

8. The apparatus of claim 4 , wherein the programmable circuitry is to:
determine effective noise errors for available Bloom filter arrays, the available Bloom filter arrays corresponding to ones of the public Bloom filter arrays and ones of the composite Bloom filter arrays that have not already been combined with other ones of the public Bloom filter arrays and have not already been combined with other ones of the composite Bloom filter arrays; and
identify a pair of the available Bloom filter arrays to combine for a next one of the successive ones of the composite Bloom filter arrays based on the effective noise errors.

9. The apparatus of claim 4 , wherein the generation of the different ones of the composite Bloom filter arrays according to the topology of the binary tree is to facilitate analysis of the public Bloom filter arrays in a piecemeal fashion that avoids non-scalable complexity.

10. The apparatus of claim 6 , wherein the first and second Bloom filter arrays and respective ones of the first and second pairs of noise probability arrays are provided by respective ones of the first and second database proprietors.

11. The apparatus of claim 6 , wherein the first pair of noise probability arrays include first values, and the second pair of noise probability arrays include second values, the first values different than the second values.

12. The apparatus of claim 5 , wherein the programmable circuitry is to repeatedly estimate the cardinality of the union of the first, second, and third Bloom filter arrays at a frequency of at least once a day.

13. At least one non-transitory computer readable storage medium comprising instructions to cause programmable circuitry to at least:
receive, via communication circuitry, a first Bloom filter array via a first network communication from a first server of a first database proprietor;
receive, via the communication circuitry, a second Bloom filter array via a second network communication from a second server of a second database proprietor; and
receive, via the communication circuitry, a third Bloom filter array from at least one of the first server, the second server, or a third server of a third database proprietor;
generate a first composite Bloom filter array based on first and second Bloom filter arrays;
generate noise arrays for the first composite Bloom filter array, the noise arrays distinct from the first Bloom filter array, distinct from the second Bloom filter array, and distinct from the first composite Bloom filter array;
generate a final composite Bloom filter array based on the first composite Bloom filter array, the noise arrays, and the third Bloom filter array, different ones of the first, second, and third Bloom filter arrays representative of different sets of users who registered with respective ones of the first, second, and third database proprietors and who 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 an overlap between the different sets of users cannot be directly determined to enable determination of an audience size across the different sets of users;
estimate a cardinality of a union of the first, second, and third Bloom filter arrays based on the final composite Bloom filter array; and
cause the communication circuitry to transmit, via a third

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/2255 Primary

  Hash tables · 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

• G06F16/2246 Primary

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

• G06F16/2456

  Join operations · CPC title

• G06F2015/763

  ASIC · CPC title