Methods and apparatus to estimate audience measurement metrics based on users represented in bloom filter arrays

Patent metadata

Field	Value
Publication number	US-11755545-B2
Application number	US-202016945055-A
Country	US
Kind code	B2
Filing date	Jul 31, 2020
Priority date	Jul 31, 2020
Publication date	Sep 12, 2023
Grant date	Sep 12, 2023

Abstract

Methods, apparatus, systems, and articles of manufacture to estimate audience measurement metrics based on users represented in Bloom filter arrays are disclosed. An apparatus includes a communications interface to receive a first Bloom filter array from a first computer of a first database proprietor. The first Bloom filter array is representative of first users who accessed media. The first users are registered with the first database proprietor. The first Bloom filter array includes a first array of first elements. Values of respective ones of the first elements are either a 0 or a 1 based on whether quantities of the first users allocated to the respective ones of the first elements are even or odd. The apparatus further includes a Bloom filter array analyzer to estimate a first cardinality for the first Bloom filter array. The first cardinality is indicative of a total number of the first users who accessed the media.

First claim

What is claimed is:

1. An apparatus comprising:
a communications interface to:
receive a first Bloom filter array from a first computer of a first database proprietor, the first Bloom filter array representative of first users who accessed media, the first users registered with the first database proprietor, the first Bloom filter array including a first array of first elements, values of respective ones of the first elements being either a 0 or a 1 based on whether quantities of the first users allocated to the respective ones of the first elements are even or odd; and
receive a second Bloom filter array from the first computer of the first database proprietor, the second Bloom filter array representative of the first users who accessed media, the second Bloom filter array including a second array of second elements, the first users allocated to ones of the first elements of the first array based on a first hash function and allocated to ones of the second elements of the second array based on a second hash function different than the first hash function; and

a Bloom filter array analyzer to:
determine a first count of the first elements with a value of 1;
determine a second count of the second elements with a value of 1; and
estimate a first cardinality for the first Bloom filter array based on an average of the first and second counts, the first cardinality indicative of a total number of the first users who accessed the media.

2. The apparatus of claim 1 , wherein the Bloom filter array analyzer is to:
determine a multiplicative constant based on a noise parameter, the noise parameter defining a probability at which ones of the values of respective ones of the first elements are flipped between 0 and 1 independent of an allocation of the first users to the respective ones of the first elements; and
estimate the first cardinality based on the multiplicative constant.

3. An apparatus comprising:
a communications interface to:
receive a first Bloom filter array from a first computer of a first database proprietor, the first Bloom filter array representative of first users who accessed media, the first users registered with the first database proprietor, the first Bloom filter array including a first array of first elements, values of respective ones of the first elements being either a 0 or a 1 based on whether quantities of the first users allocated to the respective ones of the first elements are even or odd; and
receive a second Bloom filter array from a second computer of a second database proprietor, the second Bloom filter array representative of second users who accessed the media, the second users registered with the second database proprietor, the second Bloom filter array including a second array of second elements, values of respective ones of the second elements being either a 0 or a 1 based on whether quantities of the second users allocated to the respective ones of the second elements are even or odd; and

a Bloom filter array analyzer to:
estimate an overall cardinality across both the first and second Bloom filter arrays, the overall cardinality indicative of a total number of unique individuals corresponding to the first and second users who accessed the media.

4. The apparatus of claim 3 , wherein the first array of first elements has a same length as the second array of second elements, the length corresponding to an odd number of elements.

5. The apparatus of claim 3 , wherein the Bloom filter array analyzer is to:
generate a third array of third elements based on a bit-wise union of the first array and the second array, the bit-wise union based on modulo 2 addition; and
estimate the overall cardinality based on the third array.

6. An apparatus comprising:
a communications interface is to receive a plurality of Bloom filter arrays including a first Bloom filter array, the first Bloom filter array received from a first computer of a first database proprietor, the first Bloom filter array representative of first users who accessed media, the first users registered with the first database proprietor, the first Bloom filter array including a first array of first elements, values of respective ones of the first elements being either a 0 or a 1 based on whether quantities of the first users allocated to the respective ones of the first elements are even or odd, ones of the plurality of Bloom filter arrays representative of different users who accessed the media; and
a Bloom filter array analyzer to:
generate a plurality of arrays based on bit-wise unions between different sets of at least two of the plurality of Bloom filter arrays, the bit-wise unions based on modulo 2 addition, ones of the plurality of arrays representative of exclusive-or groupings of the different users included within datasets underlying respective ones of the plurality of Bloom filter arrays;
estimate a plurality of exclusive-or cardinalities for the plurality of arrays; and
estimate an overall cardinality across the plurality of Bloom filter arrays based on a summation of the exclusive-or cardinalities.

7. A non-transitory computer readable medium comprising instructions that, when executed, cause a machine to at least:
access a first Bloom filter array generated by a first computer of a first database proprietor, the first Bloom filter array representative of first users who accessed media, the first users registered with the first database proprietor, the first Bloom filter array including a first array of first elements, values of respective ones of the first elements being either a 0 or a 1 based on whether quantities of the first users allocated to the respective ones of the first elements are even or odd;
access a second Bloom filter array generated by the first computer of the first database proprietor, the second Bloom filter array representative of the first users who accessed media, the second Bloom filter array including a second array of second elements, the first users allocated to ones of the first elements of the first array based on a first hash function and allocated to ones of the second elements of the second array based on a second hash function different than the first hash function;
determine a first count of the first elements with a value of 1;
determine a second count of the second elements with a value of 1; and
estimate a first cardinality for the first Bloom filter array based on an average of the first and second counts, the first cardinality indicative of a total number of the first users who accessed the media.

8. The non-transitory computer readable medium of claim 7 , wherein the instructions further cause the machine to:
determine a multiplicative constant based on a noise parameter, the noise parameter defining a probability at which ones of the values of respective ones of the first elements are flipped between 0 and 1 independent of an allocation of the first users to the respective ones of the first elements; and
estimate the first cardinality based on the multiplicative constant.

9. A non-transitory computer readable medium comprising instructions that, when executed, cause a machine to at least:
access a first Bloom filter array generated by a first computer of a first database proprietor, the first Bloom filter array representative of first users who accessed media, the first users registered with the first database proprietor, the first Bloom filter array including a first array of first elements, values of respective ones of the first elements being either a 0 or a 1 based on whether quantities of the first users allocated to the respective ones of the first elements are even or odd;
access a second Bloom filter array generated by a second computer of a second database prop

Assignees

• Nielsen Co Us Llc

Inventors

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

Classifications

• G06Q30/0204 Primary

  Market segmentation · CPC title

• G06F16/20 Primary

  of structured data, e.g. relational data · CPC title

• H04N21/252

  Processing of multiple end-users' preferences to derive collaborative data · CPC title

• H04N21/44224

  Monitoring of user activity on external systems, e.g. Internet browsing · CPC title

• H04N21/254

  Management at additional data server, e.g. shopping server, rights management server {(arrangements for maintenance or administration in data networks H04L41/00; network services using third party service providers H04L67/53)} · CPC title