Privacy preserving data collection and analysis
AssigneeGoogle Inc.
InventorSami Torbey
Life of this patent
Estimating the term…
Abstract
Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for preserving user privacy when collecting and analyzing user data. Methods include discarding user data after generating a privacy enhanced representation of user data and storing this privacy enhanced representation in a probabilistic data structure. Methods further preserve user privacy by inserting false negatives in the probabilistic data structure. Methods also include storing continuous value attributes in the data structure. Methods include storing date values associated with one or more user attributes. The date values may specify the date when one or more user attributes was last received.
Claims21
A computer implemented method, comprising:
- receiving, by a data processing apparatus and from a client device, user data specifying one or more attributes of a user;
- generating, by the data processing apparatus, a unique entry for the user using the user data and a user identifier unique to the user;
- inserting, by the data processing apparatus, a privacy enhanced representation of the unique entry into a probabilistic data structure that includes a plurality of privacy enhanced representations of unique entries for a plurality of users, including:
- generating, by the data processing apparatus, a hash representation of the unique entry;
- updating, by the data processing apparatus, the probabilistic data structure based on the hash representation;
- discarding, by the data processing apparatus, the user data after inserting the privacy enhanced representation of the unique entry into the probabilistic data structure;
- receiving a query requesting a response specifying how many users have an attribute that matches a given attribute specified in the query;
- obtaining, by the data processing apparatus and using the probabilistic data structure, a first number of users that includes both an estimated number of users that match the given attribute and false positives returned from the probabilistic data structure;
- and
- determining, by the data processing apparatus, the estimated number of users based on the first number of users and a false positive rate of the probabilistic data structure.
A system, comprising:
- one or more memory devices storing instructions;
- and
- one or more data processing apparatus that are configured to interact with the one or more memory devices, and upon execution of the instructions, perform operations including:
- receiving, from a client device, user data specifying one or more attributes of a user;
- generating a unique entry for the user using the user data and a user identifier unique to the user;
- inserting a privacy enhanced representation of the unique entry into a probabilistic data structure that includes a plurality of privacy enhanced representations of unique entries for a plurality of users, including:
- generating a hash representation of the unique entry;
- updating the probabilistic data structure based on the hash representation;
- discarding the user data after inserting the privacy enhanced representation of the unique entry into the probabilistic data structure;
- receiving a query requesting a response specifying how many users have an attribute that matches a given attribute specified in the query;
- obtaining, using the probabilistic data structure, a first number of users that includes both an estimated number of users that match the given attribute and false positives returned from the probabilistic data structure;
- and
- determining the estimated number of users based on the first number of users and a false positive rate of the probabilistic data structure.
A non-transitory computer readable medium storing instructions that, when executed by one or more data processing apparatus, cause the one or more data processing apparatus to perform operations comprising:
- receiving, from a client device, user data specifying one or more attributes of a user;
- generating a unique entry for the user using the user data and a user identifier unique to the user;
- inserting a privacy enhanced representation of the unique entry into a probabilistic data structure that includes a plurality of privacy enhanced representations of unique entries for a plurality of users, including:
- generating a hash representation of the unique entry;
- updating the probabilistic data structure based on the hash representation;
- discarding the user data after inserting the privacy enhanced representation of the unique entry into the probabilistic data structure;
- receiving a query requesting a response specifying how many users have an attribute that matches a given attribute specified in the query;
- obtaining, using the probabilistic data structure, a first number of users that includes both an estimated number of users that match the given attribute and false positives returned from the probabilistic data structure;
- and
- determining the estimated number of users based on the first number of users and a false positive rate of the probabilistic data structure.
Dependencies are inferred from the claim text.