System and method for generating privacy-enhanced aggregate statistics

• US 8,909,711 B1
• Filed: 06/27/2011
• Issued: 12/09/2014
• Est. Priority Date: 04/27/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Staddon, Jessica, Diwanji, Pavani Naishadh, Yung, Moti, Dulitz, Daniel
• Primary Examiner(s): Burgess, Glenton B
• Assistant Examiner(s): Nguyen, Angela
• Application Number:
  US13/169,774
• Time in Patent Office: 1,261 Days
• Field of Search: 709/205
• US Class Current: 709/205
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

A system and method for generating privacy-enhanced aggregate statistics within a social network system is provided. Data is collected and processed to gather information to generate the aggregate statistics. A threshold is assigned. The threshold includes a criterion used in making a determination on what aggregate statistic will be generated. In some embodiments, the threshold is a numerical value. In some embodiments, the numerical value, or quantitative data is then translated into qualitative descriptors. In some embodiments, noise is then added to randomize the assigned threshold. In other embodiments, noise is added to the collected data. In some embodiments, checks to guard against attacks from adversarial users are performed. Examples of indications of adversarial behavior include, but are not limited to, manipulation of profiles, continuous manipulation of affinity groups, and manipulation of preferences for one or more users. The threshold is applied and aggregate statistics are generated.

Claims

1. A computer-implemented method for generating privacy-enhanced aggregate statistics, the method comprising:

collecting data, wherein the collected data includes information related to inputs from users in a social network system;

classifying the collected data into at least one group, each group identifying a set of users sharing a common characteristic;

assigning a threshold, wherein the threshold includes a criterion for making a determination on generation of an aggregate statistic and wherein the criterion is associated with a quantitative value based on the collected data;

translating the quantitative value into a qualitative descriptor;

adding noise;

determining whether to generate the aggregate statistic based on the criterion; and

responsive to determining to generate the aggregate statistic, generating the aggregate statistic, the aggregate statistic including the qualitative descriptor and the at least one group, the qualitative descriptor representing a quantitative portion of the at least one group.

2. The method of claim 1, wherein adding noise includes adding noise to the assigned threshold to randomize the assigned threshold.

3. The method of claim 1, wherein adding noise includes adding noise to the collected data.

4. The method of claim 1, wherein adding noise includes adding noise to the quantitative value.

5. The method of claim 1, wherein the noise added is Laplace noise.

6. The method of claim 1, wherein the noise added is uniform noise.

7. The method of claim 1, further comprising:

detecting the presence of adversarial users based on user behavior; and

generating the aggregate statistic based on the presence of adversarial users.

8. The method of claim 1, wherein the user inputs include user preference indications.

9. The method of claim 7, wherein detecting the presence of adversarial users includes determining a minimum number of changes in user input to ensure that there has been enough change to necessitate a new statistic.

10. A system for generating privacy-enhanced aggregate statistics, the system comprising:

a processor; and

at least one module, stored in the memory and executed by the processor, the at least one module including instructions for;

collecting data, wherein the collected data includes information related to inputs from users in a social network system;

classifying the collected data into at least one group, each group identifying a set of users sharing a common characteristic;

assigning a threshold, wherein the threshold includes a criterion for making a determination on generation of an aggregate statistic and wherein the criterion is associated with a quantitative value based on the collected data;

translating the quantitative value into a qualitative descriptor;

adding noise;

determining whether to generate the aggregate statistic based on the criterion; and

responsive to determining to generate the aggregate statistic, generating the aggregate statistic, the aggregate statistic including the qualitative descriptor and the at least one group, the qualitative descriptor representing a quantitative portion of the at least one group.

11. The system of claim 10, wherein adding noise includes adding noise to the assigned threshold to randomize the assigned threshold.

12. The system of claim 10, wherein adding noise includes adding noise to the collected data.

13. The system of claim 10, wherein adding noise includes adding noise to the quantitative value.

14. The system of claim 10, wherein the noise added is Laplace noise.

15. The system of claim 10, wherein the noise added is uniform noise.

16. The system of claim 10 further comprising:

instructions for detecting the presence of adversarial users based on user behavior; and

generating the aggregate statistic based on the presence of adversarial users.

17. The system of claim 10 wherein the user inputs include user preference indications.

18. The system of claim 16 wherein detecting the presence of adversarial users includes determining a minimum number of changes in user input to ensure that there has been enough change to necessitate a new statistic.

19. A computer program product comprising a non-transitory computer-readable medium including instructions that, when executed by a computer, cause the computer to perform the steps comprising:

collecting data, wherein the collected data includes information related to user inputs from users in a social network system;

classifying the collected data into at least one group, each group identifying a set of users sharing a common characteristic;

generating a content information region for displaying content on a social network web site; and

generating an aggregate statistic information region adjacent to the content information region for displaying aggregate statistic information, wherein the aggregate statistic information is generated by (1) assigning a threshold, wherein the threshold includes a criterion for making a determination on generation of aggregate statistic information and wherein the criterion is associated with a quantitative value based on the collected data, (2) translating the quantitative value into a qualitative descriptor, (3) adding noise and (4) generating the aggregate statistic information based on the criterion, and the aggregate statistic information includes a qualitative descriptor representing a quantitative portion of the at least one group, the at least one group, and a description of content.

20. The computer program product of claim 19, wherein adding noise includes adding noise to the assigned threshold to randomize the assigned threshold.

21. The computer program product of claim 19, wherein adding noise includes adding noise to the collected data.

22. The computer program product of claim 19, wherein generating the aggregate statistic information region includes generating a pop-up window.

23. The computer program product of claim 22, further comprising:

receiving an input indicating a mouse-over of a portion of the aggregate statistic information region; and

in response to receiving the input, displaying a pop-up window displaying additional details associated with the aggregate statistic.