Granted Patent B2

US 12,432,217 · App. 18/394,070 · Granted Sep 30, 2025

Inventors: Gang Wang (Frederick, MD); Yue Wang (Los Altos, CA); Chin-Yet Lin (San Jose, CA)

Assignee: Google LLC

H04L63/104G06F21/6227

Abstract

Claims (66)

1. A computer-implemented method performed by a trusted server communicatively coupled to one or more digital component databases, the method comprising:

receiving, by the trusted server from a client device of a user, a request comprising a user membership probabilistic data structure encoding user membership information that indicates membership of the user in one or more user groups of a plurality of user groups, wherein each user group of the plurality of user groups has a respective unique group identifier that identifies the user group;

constructing, by the trusted server, based on the user membership probabilistic data structure, a query for identifying candidate digital components that are eligible for distribution to users that are members of the one or more user groups;

obtaining, by the trusted server, a set of candidate digital components by querying the one or more digital component databases using the constructed query, wherein each digital component database comprises a set of cells along a row or column of the digital component database for storing values of bits of the one or more respective probabilistic data structures for the digital components, the set of cells include a respective cell for each digital component in the digital component database, and the respective cell for each digital component comprises the values of the bits of at least one of the one or more respective probabilistic data structures for the digital component, and obtaining the set of candidate digital components by querying the one or more digital component databases using the constructed query comprises evaluating, for each digital component in the digital component database, a Boolean expression based on the values of the bits in the respective cell for the digital component;

selecting, from the candidate digital components, one or more digital components; and

providing the one or more digital components to the client device for presentation to the user.

2. The computer-implemented method of claim 1 , wherein the probabilistic data structure comprises one of a Bloom filter or a cuckoo filter.

3. The computer-implemented method of claim 1 , wherein each digital component database comprises the set of digital components and, for each digital component, one or more respective probabilistic data structures that each encodes a user group to which the digital component is eligible to be distributed.

4. The computer-implemented method of claim 3 , wherein constructing the query comprises generating the Boolean expression based on values of bits of the user membership probabilistic data structure and values of bits of the one or more respective probabilistic data structures for each digital component in the set of digital components.

5. The computer-implemented method of claim 4 , wherein the client device generates the user membership probabilistic data structure by:

generating, for each individual user group that includes the user as a member and using a given hash function, a hash value based on a combination of (i) the unique group identifier for the individual user group and (ii) a unique owner identifier for an owner of the individual user group;

selecting, for each hash value, a predefined number of bits of the hash value, wherein the predefined number of bits is greater than one but less than all of the bits of each hash value; and

populating the user membership probabilistic data structure using the selected predefined number of bits for each individual user group that includes the user as a member.

6. The computer-implemented method of claim 5 , wherein:

the user membership probabilistic data structure comprises a Bloom filter bit array; and

populating the user membership probabilistic data structure using the selected predefined number of bits for each individual user group that includes the user as a member comprises:

determining, using the respective predefined number of bits of the respective individual user group, a respective set of bit positions in the Bloom filter bit array; and

setting each of elements at the determined set of bit positions of the Bloom filter bit array to a value of 1.

7. The computer-implemented method of claim 6 , wherein the Boolean expression includes, for each respective probabilistic data structure of the one or more probabilistic data structures in the digital component database, a respective Boolean operation on the bits of the Bloom filter bit array and the bits in the respective probabilistic data structure.

8. The computer-implemented method of claim 5 , wherein:

the user membership probabilistic data structure comprises a cuckoo filter array; and

populating the user membership probabilistic data structure using the selected predefined number of bits for each individual user group that includes the user as a member comprises:

determining, using the respective predefined number of bits of the respective individual user group, a respective tag bit string and a set of possible positions for inserting the tag bit string into the cuckoo filter array; and

inserting the respective tag bit string into the cuckoo filter array at one of the set of possible positions.

9. The computer-implemented method of claim 8 , wherein the Boolean expression includes, for each respective probabilistic data structure of the one or more probabilistic data structures in the digital component database, a respective Boolean operation for checking tag bit string matching at the set of possible positions in the cuckoo filter array.

10. A system comprising:

one or more computers of a trusted server communicatively coupled to one or more digital component databases; and

one or more storage devices storing instructions that when executed by the one or more computers, cause the one or more computers of the trusted server to perform operations comprising:

receiving, from a client device of a user, a request comprising a user membership probabilistic data structure encoding user membership information that indicates membership of the user in one or more user groups of a plurality of user groups, wherein each user group of the plurality of user groups has a respective unique group identifier that identifies the user group;

constructing, based on the user membership probabilistic data structure, a query for identifying candidate digital components that are eligible for distribution to users that are members of the one or more user groups;

obtaining a set of candidate digital components by querying one or more digital component databases using the constructed query, wherein each digital component database comprises a set of cells along a row or column of the digital component database for storing values of bits of the one or more respective probabilistic data structures for the digital components, the set of cells include a respective cell for each digital component in the digital component database, and the respective cell for each digital component comprises the values of the bits of at least one of the one or more respective probabilistic data structures for the digital component, and obtaining the set of candidate digital components by querying the one or more digital component databases using the constructed query comprises evaluating, for each digital component in the digital component database, a Boolean expression based on the values of the bits in the respective cell for the digital component;

selecting, from the candidate digital components, one or more digital components; and

providing the one or more digital components to the client device for presentation to the user.

11. The system of claim 10 , wherein the probabilistic data structure comprises one of a Bloom filter or a cuckoo filter.

12. The system of claim 10 , wherein each digital component database comprises a set of digital components and, for each digital component, one or more respective probabilistic data structures that each encodes a user group to which the digital component is eligible to be distributed.

13. The system of claim 12 , wherein constructing the query comprises generating the Boolean expression based on values of bits of the user membership probabilistic data structure and values of bits of the one or more respective probabilistic data structures for each digital component in the set of digital components.

14. The system of claim 13 , wherein the client device generates the user membership probabilistic data structure by:

generating, for each individual user group that includes the user as a member and using a given hash function, a hash value based on a combination of (i) the unique group identifier for the individual user group and (ii) a unique owner identifier for an owner of the individual user group;

selecting, for each hash value, a predefined number of bits of the hash value, wherein the predefined number of bits is greater than one but less than all of the bits of each hash value; and

populating the user membership probabilistic data structure using the selected predefined number of bits for each individual user group that includes the user as a member.

15. The system of claim 14 , wherein:

the user membership probabilistic data structure comprises a Bloom filter bit array; and

populating the user membership probabilistic data structure using the selected predefined number of bits for each individual user group that includes the user as a member comprises:

determining, using the respective predefined number of bits of the respective individual user group, a respective set of bit positions in the Bloom filter bit array; and

setting each of elements at the determined set of bit positions of the Bloom filter bit array to a value of 1.

16. The system of claim 15 , wherein the Boolean expression includes, for each respective probabilistic data structure of the one or more probabilistic data structures in the digital component database, a respective Boolean operation on the bits of the Bloom filter bit array and the bits in the respective probabilistic data structure.

17. The system of claim 14 , wherein:

the user membership probabilistic data structure comprises a cuckoo filter array; and

populating the user membership probabilistic data structure using the selected predefined number of bits for each individual user group that includes the user as a member comprises:

determining, using the respective predefined number of bits of the respective individual user group, a respective tag bit string and a set of possible positions for inserting the tag bit string into the cuckoo filter array; and

inserting the respective tag bit string into the cuckoo filter array at one of the set of possible positions.

18. One or more non-transitory computer-readable storage media storing instructions that, when executed by one or more computers, cause the one or more computers of a trusted server communicatively coupled to one or more digital component databases to perform operations comprising:

receiving, from a client device of a user, a request comprising a user membership probabilistic data structure encoding user membership information that indicates membership of the user in one or more user groups of a plurality of user groups, wherein each user group of the plurality of user groups has a respective unique group identifier that identifies the user group;

constructing, based on the user membership probabilistic data structure, a query for identifying candidate digital components that are eligible for distribution to users that are members of the one or more user groups;

obtaining a set of candidate digital components by querying one or more digital component databases using the constructed query, wherein each digital component database comprises a set of cells along a row or column of the digital component database for storing values of bits of the one or more respective probabilistic data structures for the digital components, the set of cells include a respective cell for each digital component in the digital component database, and the respective cell for each digital component comprises the values of the bits of at least one of the one or more respective probabilistic data structures for the digital component, and obtaining the set of candidate digital components by querying the one or more digital component databases using the constructed query comprises evaluating, for each digital component in the digital component database, a Boolean expression based on the values of the bits in the respective cell for the digital component;

selecting, from the candidate digital components, one or more digital components; and

providing the one or more digital components to the client device for presentation to the user.

19. A computer-implemented method performed by a trusted server communicatively coupled to one or more digital component databases, the method comprising:

receiving, by the trusted server from a client device of a user, a request comprising a user membership probabilistic data structure encoding user membership information that indicates membership of the user in one or more user groups of a plurality of user groups, wherein each user group of the plurality of user groups has a respective unique group identifier that identifies the user group, wherein the client device generates the user membership probabilistic data structure by:

generating, for each individual user group that includes the user as a member and using a given hash function, a hash value based on a combination of (i) the unique group identifier for the individual user group and (ii) a unique owner identifier for an owner of the individual user group;

selecting, for each hash value, a predefined number of bits of the hash value, wherein the predefined number of bits is greater than one but less than all of the bits of each hash value; and

populating the user membership probabilistic data structure using the selected predefined number of bits for each individual user group that includes the user as a member;

constructing, by the trusted server, based on the user membership probabilistic data structure, a query for identifying candidate digital components that are eligible for distribution to users that are members of the one or more user groups;

obtaining a set of candidate digital components by querying one or more digital component databases using the constructed query;

selecting, from the candidate digital components, one or more digital components; and

providing the one or more digital components to the client device for presentation to the user.

Assignments (2)

Continuity (2)

References Cited (22)