METHODS AND APPARATUS TO ESTIMATE CARDINALITY OF USERS REPRESENTED IN ARBITRARILY DISTRIBUTED BLOOM FILTERS
Methods, apparatus, systems, and articles of manufacture to estimate cardinality of users represented in arbitrarily distributed bloom filter arrays are disclosed. A system includes a communication interface to: access a first Bloom filter array representative of first entries in a first database, the first entries allocated to ones of first elements in the first Bloom filter array based on a non-uniform distribution of outputs of a hash function applied to the first entries, and access a second Bloom filter array representative of second entries in a second database. The system also includes machine readable instructions to cause one or more processors to estimate a cardinality of a union of the first and second entries based on the non-uniform distribution of the outputs of the hash function.
1 . A computing system comprising a processor and a memory, the computing system configured to perform a set of acts comprising:
accessing a first Bloom filter array generated by a first computing system of a first database proprietor, wherein the first Bloom filter array is representative of first entries in a first database of the first database proprietor, wherein the first entries are allocated to respective elements in the first Bloom filter array using a hash function, and wherein a mapping of an output of the hash function to an element in the first Bloom filter array is based on a non-uniform distribution across different elements in the first Bloom filter array;
accessing a second Bloom filter array generated by a second computing system, wherein the second Bloom filter array is representative of second entries in a second database, wherein the second entries are allocated to respective elements in the second Bloom filter using the hash function, and wherein a mapping of an output of the hash function to an element in the second Bloom filter array is based on the non-uniform distribution; and
estimating a cardinality of a union of the first and second entries based on the non-uniform distribution,
wherein the first Bloom filter array represents at least a same amount of data with a smaller array length as compared to a length of a traditional Bloom filter array that is populated using a uniform distribution, because the non-uniform distribution reduces a likelihood of the first Bloom filter array becoming saturated as compared to a likelihood of the traditional Bloom filter array becoming saturated.
2 . The computing system of claim 1 , wherein the first and second entries correspond to users who accessed media, a smallest one of the different sized proportions being greater than or equal to a threshold defined based on a universe estimate of a population of possible audience members of the media.
3 . The computing system of claim 1 , wherein estimating the cardinality comprises causing a numerical solver to solve for a number of entries that maximizes a likelihood of producing the union of the first and second entries.
4 . The computing system of claim 1 , wherein the estimate of the cardinality has an error, for a given amount of noise in ones of the first and second Bloom filter arrays, that has an absolute value that varies by less than 1% across a range of different values of a ratio of the cardinality to a length of the first and second Bloom filter arrays, the different values ranging from 0.125 to 8.
5 . The computing system of claim 1 , wherein the cardinality is a first cardinality and the union is a first union, and wherein the set of acts further comprises estimating a second cardinality of a second union of entries in the first and second Bloom filter arrays and at least one other Bloom filter array.
6 . The computing system of claim 1 , wherein the non-uniform distribution is a geometric distribution.
7 . A method comprising:
accessing, by a computing system, a first Bloom filter array generated by a first computing system of a first database proprietor, wherein the first Bloom filter array is representative of first entries in a first database of the first database proprietor, wherein the first entries are allocated to respective elements in the first Bloom filter array using a hash function, and wherein a mapping of an output of the hash function to an element in the first Bloom filter array is based on a non-uniform distribution across different elements in the first Bloom filter array;
accessing, by the computing system, a second Bloom filter array generated by a second computing system, wherein the second Bloom filter array is representative of second entries in a second database, wherein the second entries are allocated to respective elements in the second Bloom filter using the hash function, and wherein a mapping of an output of the hash function to an element in the second Bloom filter array is based on the non-uniform distribution; and
estimating, by the computing system, a cardinality of a union of the first and second entries based on the non-uniform distribution,
wherein the first Bloom filter array represents at least a same amount of data with a smaller array length as compared to a length of a traditional Bloom filter array that is populated using a uniform distribution, because the non-uniform distribution reduces a likelihood of the first Bloom filter array becoming saturated as compared to a likelihood of the traditional Bloom filter array becoming saturated.
8 . The method of claim 7 , wherein the first and second entries correspond to users who accessed media, a smallest one of the different sized proportions being greater than or equal to a threshold defined based on a universe estimate of a population of possible audience members of the media.
9 . The method of claim 7 , wherein estimating the cardinality comprises causing a numerical solver to solve for a number of entries that maximizes a likelihood of producing the union of the first and second entries.
10 . The method of claim 7 , wherein the estimate of the cardinality has an error, for a given amount of noise in ones of the first and second Bloom filter arrays, that has an absolute value that varies by less than 1% across a range of different values of a ratio of the cardinality to a length of the first and second Bloom filter arrays, the different values ranging from 0.125 to 8.
11 . The method of claim 7 , wherein the cardinality is a first cardinality and the union is a first union, and wherein the method further comprises estimating a second cardinality of a second union of entries in the first and second Bloom filter arrays and at least one other Bloom filter array.
12 . The method of claim 7 , wherein the non-uniform distribution is a geometric distribution.
13 . A non-transitory computer-readable medium having stored thereon instructions that when executed by a computing system cause the computing system to perform a set of acts comprising:
accessing a first Bloom filter array generated by a first computing system of a first database proprietor, wherein the first Bloom filter array is representative of first entries in a first database of the first database proprietor, wherein the first entries are allocated to respective elements in the first Bloom filter array using a hash function, and wherein a mapping of an output of the hash function to an element in the first Bloom filter array is based on a non-uniform distribution across different elements in the first Bloom filter array;
accessing a second Bloom filter array generated by a second computing system, wherein the second Bloom filter array is representative of second entries in a second database, wherein the second entries are allocated to respective elements in the second Bloom filter using the hash function, and wherein a mapping of an output of the hash function to an element in the second Bloom filter array is based on the non-uniform distribution; and
estimating a cardinality of a union of the first and second entries based on the non-uniform distribution,
wherein the first Bloom filter array represents at least a same amount of data with a smaller array length as compared to a length of a traditional Bloom filter array that is populated using a uniform distribution, because the non-uniform distribution reduces a likelihood of the first Bloom filter array becoming saturated as compared to a likelihood of the traditional Bloom filter array becoming saturated.
14 . The non-transitory computer-readable medium of claim 13 , wherein the first and second entries correspond to users who accessed media, a smallest one of the different sized proportions being greater than or equal to a threshold defined based on a universe estimate of a population of possible audience members of the media.
15 . The non-transitory computer-readable medium of claim 13 , wherein estimating the cardinality comprises causing a numerical solver to solve for a number of entries that maximizes a likelihood of producing the union of the first and second entries.
16 . The non-transitory computer-readable medium of claim 13 , wherein the estimate of the cardinality has an error, for a given amount of noise in ones of the first and second Bloom filter arrays, that has an absolute value that varies by less than 1% across a range of different values of a ratio of the cardinality to a length of the first and second Bloom filter arrays, the different values ranging from 0.125 to 8.
17 . The non-transitory computer-readable medium of claim 13 , wherein the cardinality is a first cardinality and the union is a first union, and wherein the set of acts further comprises estimating a second cardinality of a second union of entries in the first and second Bloom filter arrays and at least one other Bloom filter array.
18 . The non-transitory computer-readable medium of claim 13 , wherein the non-uniform distribution is a geometric distribution.