IP Library › Granted Patent US 12,387,227
Granted Patent B2
US 12,387,227 · App. 18/298,814 · Granted Aug 12, 2025

Methods and apparatus to estimate cardinality of users represented in arbitrarily distributed bloom filters

Inventors: Jonathan Sullivan (Hurricane, UT); Diane Morovati Lopez (West Hills, CA); Christie Summers (Baltimore, MD); Jake Ryan Dailey (San Francisco, CA); Michael R. Sheppard (Holland, MI); DongBo Cui (Fresh Meadows, NY)
Assignee: The Nielsen Company (US), LLC
G06Q30/0201G06N7/01
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,387,227
App. No.
18/298,814
Granted
Aug 12, 2025
Kind
B2
Abstract

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.

Claims (30)

1. A system comprising:

a communication interface to:

access a first Bloom filter array generated by a first computer of a first database proprietor, the first Bloom filter array representative of first entries in a first database of the first database proprietor, 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 generated by a second computer of a second database proprietor, the second Bloom filter array representative of second entries in a second database of the second database proprietor, the second entries allocated to ones of second elements in the second Bloom filter array based on the non-uniform distribution of the outputs of the hash function applied to the second entries;

one or more processors; and

machine readable instructions to cause the 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,

wherein the non-uniform distribution is a geometric distribution in which a leftmost bit of a Bloom filter array has a highest probability of mapping a hash function output, with the probability decreasing for subsequent bits of the Bloom filter array, such that the Bloom filter array represents at least a same amount of data with a smaller array length as compared to a length of traditional Bloom filter array that is populated using a uniform distribution, and a likelihood of the Bloom filter array becoming saturated is reduced as compared to a likelihood of the traditional Bloom filter array becoming saturated.

2. The system of claim 1 , wherein the first and second entries correspond to users who accessed media.

3. The system of claim 1 , wherein the one or more processors are to estimate the cardinality by 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 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 system of claim 1 , wherein the cardinality is a first cardinality and the union is a first union, the one or more processors to estimate 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. A method comprising:

accessing a first Bloom filter array generated by a first computer of a first database proprietor, the first Bloom filter array representative of first entries in a first database of the first database proprietor, 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;

accessing a second Bloom filter array generated by a second computer of a second database proprietor, the second Bloom filter array representative of second entries in a second database of the second database proprietor, the second entries allocated to ones of second elements in the second Bloom filter array based on the non-uniform distribution of the outputs of the hash function applied to the second entries; and

estimating a cardinality of a union of the first and second entries based on the non-uniform distribution of the outputs of the hash function,

wherein the non-uniform distribution is a geometric distribution in which a leftmost bit of a Bloom filter array has a highest probability of mapping a hash function output, with the probability decreasing for subsequent bits of the Bloom filter array, such that the Bloom filter array represents at least a same amount of data with a smaller array length as compared to a length of traditional Bloom filter array that is populated using a uniform distribution, and a likelihood of the Bloom filter array becoming saturated is reduced as compared to a likelihood of the traditional Bloom filter array becoming saturated.

7. The method of claim 6 , wherein the first and second entries correspond to users who accessed media.

8. The method of claim 6 , further including estimating the cardinality by causing a numerical solver to solve for a few entries that maximizes a likelihood of producing the union of the first and second entries.

9. The method of claim 6 , wherein the estimate of the cardinality has an error that remains substantially consistent, for a given amount of noise in ones of the first and second Bloom filter arrays, 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.

10. The method of claim 6 , wherein the cardinality is a first cardinality, and the union is a first union, the method further including 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.

11. A system comprising:

a communication interface to:

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 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 users, and

access a second Bloom filter array generated by a second computer of a second database proprietor, the second Bloom filter array representative of second users who accessed media, the second users allocated to ones of second elements in the second Bloom filter array based on the non-uniform distribution of the outputs of the hash function applied to the second users;

one or more processors; and

machine readable instructions to cause the one or more processors to estimate a cardinality of a union of the first and second users based on the non-uniform distribution of the outputs of the hash function,

wherein the non-uniform distribution is a geometric distribution in which a leftmost bit of a Bloom filter array has a highest probability of mapping a hash function output, with the probability decreasing for subsequent bits of the Bloom filter array, such that the Bloom filter array represents at least a same amount of data with a smaller array length as compared to a length of traditional Bloom filter array that is populated using a uniform distribution, and a likelihood of the Bloom filter array becoming saturated is reduced as compared to a likelihood of the traditional Bloom filter array becoming saturated.

12. The system of claim 11 , wherein a smallest one of the different sized proportions is greater than or equal to a threshold defined based on a universe estimate of a population of possible audience members of the media.

13. The system of claim 11 , wherein the one or more processors are to estimate the cardinality by causing a numerical solver to solve for several users that maximizes a likelihood of producing the union of the first and second users.

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

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 20, 2023
From: SUMMERS, CHRISTIE; CUI, DONGBO; DAILEY, JAKE RYAN; LOPEZ, DIANE MOROVATI; SHEPPARD, MICHAEL
To: THE NIELSEN COMPANY (US), LLC
Reel/Frame 063710/0259 →
INVENTION DISCLOSURE FORM Recorded May 20, 2023
From: SULLIVAN, JONATHAN
To: THE NIELSEN COMPANY (US), LLC
Reel/Frame 063710/0302 →
Continuity (3)
Continuation 17007774 · Aug 31, 2020
Provisional Application 62975020 · Feb 11, 2020
Related Publication 20230245145A1 · Aug 3, 2023
References Cited (74)
US 6108637A · Blumenau · 2000 [cited by applicant]
US 8370489B2 · Mazumdar et al. · 2013 [cited by applicant]
US 8600921B2 · Burkard et al. · 2013 [cited by applicant]
US 8930701B2 · Burbank et al. · 2015 [cited by applicant]
US 9237138B2 · Bosworth et al. · 2016 [cited by applicant]
US 9361322B1 · Dutta et al. · 2016 [cited by applicant]
US 9596202B1 · Beach et al. · 2017 [cited by applicant]
US 9600921B2 · Thomaszewski et al. · 2017 [cited by applicant]
US 10963922B1 · Andersen et al. · 2021 [cited by applicant]
US 11216588B1 · An · 2022 [cited by examiner]
US 11676160B2 · Sullivan et al. · 2023 [cited by applicant]
US 11741068B2 · Sheppard et al. · 2023 [cited by applicant]
US 20090296594A1 · Cao · 2009 [cited by examiner]
US 20100070514A1 · Woodruff · 2010 [cited by applicant]
US 20140149433A1 · Lakshminarayan · 2014 [cited by applicant]
US 20150178769A1 · Mirisola et al. · 2015 [cited by applicant]
US 20160048868A1 · Mirisola et al. · 2016 [cited by applicant]
US 20160188623A1 · Finlay · 2016 [cited by examiner]
US 20160292716A1 · Mirisola et al. · 2016 [cited by applicant]
US 20170103417A1 · Nguyen et al. · 2017 [cited by applicant]
US 20170323200A1 · Corvinelli · 2017 [cited by examiner]
US 20180349364A1 · Arnold · 2018 [cited by applicant]
US 20190026221A1 · Bar-Joshua · 2019 [cited by applicant]
US 20190272388A1 · Tsou et al. · 2019 [cited by applicant]
US 20200007919A1 · Sheppard et al. · 2020 [cited by applicant]
US 20210117428A1 · Dalgliesh · 2021 [cited by applicant]
US 20210248629A1 · Sullivan et al. · 2021 [cited by applicant]
US 20210359836A1 · Wright et al. · 2021 [cited by applicant]
US 20210359846A1 · Wright et al. · 2021 [cited by applicant]
US 20210406240A1 · Sheppard et al. · 2021 [cited by applicant]
US 20220036390A1 · Sheppard et al. · 2022 [cited by applicant]
US 20220084074A1 · Maddern et al. · 2022 [cited by applicant]
US 20220138831A1 · Yoo · 2022 [cited by applicant]
US 20220261853A1 · Publicover et al. · 2022 [cited by applicant]
US 20230004997A1 · Sheppard et al. · 2023 [cited by applicant]
CN 106874165A · 2017 [cited by applicant]
JP 2011182163A · 2011 [cited by applicant]
Geiringer, “On the Probability Theory of Arbitrarily Linked Events,” Institute of Mathematical Statistics, Dec. 1938, 12 pages. [cited by applicant]
Bloom, “Space/Time Trade-offs in Hash Coding Errors,” Computer Usage Company, vol. 13, No. 7, Jul. 1970, 5 pages. [cited by applicant]
Johnson et al., “Urn Models and Their Application an Approach to Modern Discrete Probability Theory,” John Wiley & Sons, Inc., 1977, 413 pages. [cited by applicant]
Broder et al., “Network Application of Bloom Filters: A Survey”, Internet Mathematics, vol. 1, No. 4, Apr. 14, 2004, 25 pages. [cited by applicant]
Swamidass et al., “Mathematical Correction for Fingerprint Similarity Measures to Improve Chemical Retrieval,” J. Chem. Inf. Model 2007, Nov. 20, 2006, 13 pages. [cited by applicant]
Many et al., “Fast Private Set Operations with SEPIA,” Mar. 1, 2012, 11 pages. [cited by applicant]
Tschorsch et al., “An Algorithm for Privacy-Preserving Distributed User Statistics,” Computer Engineering Group, Humboldt University of Berlin, Unter den Linden 6, DE 10099 Berlin, Germany, Jul. 1, 2013, 13 pages. [cited by applicant]
Erlingsson et al., “RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response,” Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security Nov. 2014, 14 pages. [cited by applicant]
Dong et al., “Approximating Private Set Union Intersection Cardinality with Logarithmic Complexity,” IEEE Transactions on Information Forensics and Security, Jun. 28, 2017, 20 pages. [cited by applicant]
Kanaujia et al., “Exploring Probabilistic Data Structures: Bloom Filters,” May 2, 2018, 7 pages. [cited by applicant]
Shi et al., “Audience Size Forecasting,” KDD 2018, Aug. 2018, 10 pages. [cited by applicant]
Stritzl, “Privacy Preserving Matching Using Bloom Filters; An Analysis and an Encrypted Variant”, University of Twente, Apr. 4, 2019, 31 pages. [cited by applicant]
Wikipedia, “Differential Privacy,” available at https://en.wikipedia.org/wiki/Differential_privacy, last edited Aug. 26, 2023, 12 pages. [cited by applicant]
Wikipedia, “Brent's Method,” available at https://en.wikipedia.org/wiki/Brent%27s_method, last edited Aug. 9, 2022, 6 pages. [cited by applicant]
Wikipedia, “Bloom Filter,” available at https://en.wikipedia.org/wiki/Bloom_filter, last edited Sep. 6, 2023, 21 pages. [cited by applicant]
Wright et al., “Privacy-Preserving Secure Cardinality and Frequency Estimation,” Google LLC, May 29, 2020, 20 pages. [cited by applicant]
Linearlegions, “A Linear Size Cardinality Estimator” Technical Disclosure Commons, available at https://www.tdcommons.org/dpubs_series/3830, Nov. 29, 2020, 20 pages. [cited by applicant]
International Searching Authority, “Written Opinion,” issued in connection with International Patent Application No. PCT/US2021/016773, mailed on May 25, 2021, 3 Pages. [cited by applicant]
International Searching Authority, “International Search Report,” issued in connection with International Patent Application No. PCT/US2021/016773, mailed on May 25, 2021, 3 pages. [cited by applicant]
International Searching Authority, “International Preliminary Report on Patentability,” issued in connection with International Patent Application No. PCT/US2021/016773, issued on Aug. 11, 2022, 4 pages. [cited by applicant]
United States Patent and Trademark Office, “Non-Final Office Action,” issued in connection with U.S. Appl. No. 17/362,404, mailed on Sep. 13, 2022, 24 pages. [cited by applicant]
United States Patent and Trademark Office, “Non-Final Office Action,” issued in connection with U.S. Appl. No. 16/945,055, mailed on Sep. 15, 2022, 8 pages. [cited by applicant]
United States Patent and Trademark Office, “Non-Final Office Action,” issued in connection with U.S. Appl. No. 17/362,419, mailed on Dec. 5, 2022, 12 pages. [cited by applicant]
United States Patent and Trademark Office, “Final Office Action,” issued in connection with U.S. Appl. No. 16/945,055, mailed on Jan. 26, 2023, 8 pages. [cited by applicant]
United States Patent and Trademark Office, “Final Office Action,” issued in connection with U.S. Appl. No. 17/362,404, mailed on Feb. 21, 2023, 21 pages. [cited by applicant]
Egert et al., “Privately Computing Set-Union and Set-Intersection Cardinality via Bloom Filters,” Information Security and Privacy, Jan. 2015, pp. 413-430. [cited by applicant]
Harmouch et al., “Cardinality Estimation: An Experimental Survey,” Proceedings of the VLDB Endowment, Dec. 2017, vol. 11, Issue 4, 14 pages. [cited by applicant]
United States Patent and Trademark Office, “Non-Final Office Action,” issued in connection with U.S. Appl. No. 17/007,774, mailed on Feb. 17, 2022, 12 pages. [cited by applicant]
United States Patent and Trademark Office, “Final Office Action,” issued in connection with U.S. Appl. No. 17/007,774, mailed on Jul. 1, 2022, 18 pages. [cited by applicant]
United States Patent and Trademark Office, “Advisory Action,” issued in connection with U.S. Appl. No. 17/007,774, mailed on Oct. 31, 2022, 3 pages. [cited by applicant]
United States Patent and Trademark Office, “Notice of Allowance and Fee(s) Due,” issued in connection with U.S. Appl. No. 17/007,774, mailed on Jan. 11, 2023, 8 pages. [cited by applicant]
United States Patent and Trademark Office, “Notice of Allowance and Fee(s) Due,” issued in connection with U.S. Appl. No. 17/362,419, mailed on Apr. 3, 2023, 6 pages. [cited by applicant]
United States Patent and Trademark Office, “Notice of Allowance and Fee(s) Due,” issued in connection with U.S. Appl. No. 16/945,055, mailed on Apr. 21, 2023, 10 pages. [cited by applicant]
United States Patent and Trademark Office, “Advisory Action,” issued in connection with U.S. Appl. No. 17/362,404, mailed on May 2, 2023, 3 pages. [cited by applicant]
United States Patent and Trademark Office, “Supplemental Notice of Allowability,” issued in connection with U.S. Appl. No. 16/945,055, mailed on May 17, 2023, 8 pages. [cited by applicant]
United States Patent and Trademark Office, “Supplemental Notice of Allowability,” issued in connection with U.S. Appl. No. 16/945,055, mailed on Jun. 12, 2023, 8 pages. [cited by applicant]
Xue, Qiao et al., “Distributed Set Intersection and Union with Local Differential Privacy,” 2017 IEEE 23rd International Conference on Parallel and Distributed Systems (ICPADS), Dec. 2017, Shenzen, China, pp. 198-205. [cited by applicant]