# US 2021/0004487 A1 · Systems and methods for privacy preserving determination of intersections of sets of user identifiers

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0004487 A1
- Document ID: US20210004487A1
- Status: Published application
- Kind: A1
- Application number: 16/592,190
- Filed: 2019-10-03
- Published: 2021-01-07
- Earliest claimed: 2019-07-05
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Michael DAUB; Scott SCHNEIDER; Joseph sean Cahill Goodknight KNIGHTBROOK; Sheng MA; Laura BOOK
- Web page: https://patentgrep.com/patent/US20210004487A1

## CPC

- G06F 21/6254: {by anonymising data, e.g. decorrelating personal data from the owner's identification}
- G06Q 30/0242: Determining effectiveness of advertisements
- G06F 16/212: {with details for data modelling support}
- G06F 16/2255: {Hash tables}
- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- G06Q 30/0246: {Traffic}
- G06Q 30/0277: {Online advertisement}
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- H04L 63/0407: {wherein the identity of one or more communicating identities is hidden (cryptographic mechanisms or cryptographic arrangements for anonymous credentials or for identity based cryptographic systems H04L9/00)}
- H04L 63/0428: {wherein the data content is protected, e.g. by encrypting or encapsulating the payload}
- H04W 12/02: Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

At least one aspect is directed to determining an estimate of an intersection of user identifiers in a first set of user identifiers and a second set of user identifiers. The first and second sets of user identifiers can be populated with user identifiers that have interacted with the same content item or content item campaign. Estimates of intersections of the first and the second sets can be determined based on a binomial vector approach, a vector of counts approach, or a hybrid approach. The binomial vector approach generates vectors based on k hashes of each user identifier in the first set and summing the vectors to generate a first vector. The intersection can be determined based on a dot product of the first vector and a second vector similarly generated from the second set of user identifiers.

## Claims

### Claim 1

A method for providing anonymous data about user interactions with a set of content items, the method comprising:
receiving, via a network, data to identify a set of hash functions;
retrieving a plurality of user identifiers, each of the user identifiers identifying interaction with a set of content items by a respective user of the plurality;
for each of the plurality of user identifiers:
generating a hash value of the user identifier using the hash function included in the request;
determining a value of m-bits of the hash value, and
incrementing a count of a register corresponding to the value, the register being one of k registers;
generating an interaction vector, each coordinate of the interaction vector being equal to a count of a corresponding kth register; and
transmitting, via a network, the generated interaction vector.

### Claim 2 (depends on 1)

The method of claim 1, wherein receiving, via a network, data to identify the list of hash functions includes receiving data to identify a set of content items.

### Claim 3 (depends on 2)

The method of claim 2, wherein retrieving the plurality of user identifiers, each of the user identifiers identifying interaction with the set of content items by a respective user of the plurality includes only retrieving the plurality of user identifiers that identify interaction with the set of content items identified by the received data.

### Claim 4 (depends on 1)

The method of claim 1, comprising:
generating p hash values for each of the plurality of the user identifiers, wherein the p hash values correspond to a respective hash function in the set of hash functions,
determining the value of m-bits for each of the p hash values, and incrementing the count of a register corresponding to the value, the register being one of k registers, where k=2{circumflex over ( )}m, where each of the p hash values corresponds to a set of k registers.

### Claim 5 (depends on 4)

The method of claim 4, wherein generating the interaction vector comprises generating p interaction vectors, wherein each coordinate of the p interaction vectors corresponds to the kth register in the pth set of registers.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining the value of m-bits of the hash value comprises determining the m least significant bits of the hash value.

### Claim 7 (depends on 1)

The method of claim 1, wherein generating the interaction vector, each coordinate of the interaction vector being equal to the count of the corresponding kth register includes subtracting, from each coordinate of the interaction vector, a value equal to the number of user identifiers divided by k.

### Claim 8 (depends on 1)

The method of claim 1, wherein generating the interaction vector, each coordinate of the interaction vector being equal to the count of a corresponding kth register includes adding, to each coordinate of the interaction vector, a noise function based on one or more parameters.

### Claim 9 (depends on 1)

The method of claim 1, wherein transmitting, via a network, the generated interaction vector includes transmitting the number of user identifiers identifying interaction with the set of content items.

### Claim 10 (depends on 5)

The method of claim 5, wherein transmitting, via a network, the generated interaction vector includes transmitting p interaction vectors.

### Claim 11

A system comprising one or more processors, the processors configured to:
receive, via a network, data to identify a set of hash functions;
retrieve a plurality of user identifiers, each of the user identifiers identifying interaction with a set of content items by a respective user of the plurality;
for each of the plurality of user identifiers:
generate a hash value of the user identifier using the hash function included in the request;
determine a value of a first m-bits of the hash value, and
increment a count of a register corresponding to the value, the register being one of k registers;
generate an interaction vector, each coordinate of the interaction vector being equal to a count of a corresponding kth register; and
transmit, via a network, the generated interaction vector.

### Claim 12 (depends on 11)

The system of claim 11, wherein the one or more processors are configured to:
receive, via a network, data to identify the list of hash functions, and receive data to identify the set of content items.

### Claim 13 (depends on 12)

The system of claim 12, wherein the one or more processors are configured to:
retrieve only the plurality of user identifiers that identify interaction with the set of content items identified by the received data.

### Claim 14 (depends on 11)

The system of claim 11, wherein the one or more processors are configured to:
generate p hash values for each of the plurality of the user identifiers, wherein the p hash values correspond to a respective hash function in the set of hash functions,
determine the value of m-bits for each of the p hash values, and
increment the count of a register corresponding to the value, the register being one of k registers, where k=2{circumflex over ( )}m, where each of the p hash values corresponds to a set of k registers.

### Claim 15 (depends on 14)

The system of claim 14, wherein the one or more processors are configured to: generate p interaction vectors, wherein each coordinate of the p interaction vectors corresponds to the kth register in the pth set of registers.

### Claim 16 (depends on 11)

The system of claim 11, wherein the one or more processors are configured to:
determine the value of m-bits of the hash value by determining the m least significant bits of the hash value.

### Claim 17 (depends on 11)

The system of claim 11, wherein the one or more processors are configured to:
generate an interaction vector, each coordinate of the interaction vector being equal to the count of the corresponding kth register, and subtract, from each coordinate of the interaction vector, a value equal to the number of user identifiers divided by k.

### Claim 18 (depends on 11)

The system of claim 11, wherein the one or more processors are configured to:
generate the interaction vector, each coordinate of the interaction vector being equal to the count of the corresponding kth register, and add, to each coordinate of the interaction vector, a noise function based on one or more parameters.

### Claim 19 (depends on 11)

The system of claim 11, wherein the one or more processors are configured to:
transmit, via a network, the generated interaction vector and the number of user identifiers identifying interaction with the set of content items.

### Claim 20 (depends on 15)

The system of claim 15, wherein the one or more processors are configured to:
transmit, via a network, the generated p interaction vectors.
