Privacy-preserving collaborative filtering

• US 8,478,768 B1
• Filed: 12/08/2011
• Issued: 07/02/2013
• Est. Priority Date: 12/08/2011
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Pathak, Manas Ashok, Chow, Richard, Shi, Runting, Wang, Cong
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Weinrich, Brian E.
• Application Number:
  US13/314,748
• Publication Number:
  US 20130151540A1
• Time in Patent Office: 572 Days
• Field of Search: 707/757, 707/754
• US Class Current: 707/757
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06Q 30/0282 Rating or review of business operators or products

Abstract

A recommender system can generate a predicted item rating for one user by performing collaborative filtering on item ratings from other users. The recommender system can include a client device that interfaces with a server to obtain a predicted item rating for a local user. The client device can generate a standardized ratings vector for the user, and computes a group identifier for the user based on the standardized ratings vector. The system also generates a noisy ratings vector for the local user, and sends a user-ratings snapshot to a recommendation server that includes the group identifier and the noisy ratings vector. The recommender system can also include the recommendation server that generates a predicted item rating for the user by performing collaborative filtering on ratings vectors from a plurality of other users that belong to the same ratings group.

Claims

1. A computer-implemented method comprising:

receiving a user-ratings snapshot, wherein the user-ratings snapshot comprises a first group identifier for a first end-user and a first ratings vector for the first end-user, and wherein the ratings vector indicates a rating value for each of a plurality of rated items;

associating the first ratings vector to a ratings group identified by the first group identifier;

receiving a recommendation request indicating a second group identifier for a second end-user, wherein the second group identifier identifies the ratings group;

determining a plurality of ratings vectors associated with the ratings group; and

generating, by a computing device, a recommendation based on the plurality of ratings vectors, wherein generating the recommendation involves;

determining, from the plurality of ratings vectors, a corresponding plurality of standardized ratings for a rated item of one or more rated items, wherein a standardized rating from a respective end-user is standardized based on a rating average for the respective end-user;

computing a standardized average rating for the rated item by computing the average for the plurality of standardized ratings;

computing an average rating for the rated item by adding the second end-user'"'"'s average rating to the standardized average rating; and

selecting an item that has the highest average rating among the one or more rated items.

2. The method of claim 1, wherein the ratings group is identified by a plurality of encrypted group identifiers,

wherein the first and second group identifiers each comprise a group identifier which has been encrypted using a shared key corresponding to the first and second users, and

wherein the method further comprises determining that the second end-user is associated with the ratings group by determining that the second group identifier matches at least the first group identifier.

3. The method of claim 1, further comprising:

responsive to determining that the first group identifier for the first end-user does not match a group identifier of an existing ratings group;

creating a ratings group corresponding to the first group identifier; and

associating the ratings group with the first group identifier.

4. The method of claim 1, further comprising:

generating a group-identifying hash function; and

sending the group-identifying hash function to a plurality of entities.

5. The method of claim 4, wherein generating the group-identifying hash function involves:

generating a set of k random vectors, wherein a respective vector includes m random values, and wherein the respective random vector is orthogonal to other random vectors in the set;

normalizing the random vectors in the set to produce unit-length random vectors; and

generating the group-identifying hash function based on the set of k unit-length random vectors, wherein the group-identifying hash function maps an m-dimensional ratings vector into a k-bit string.

6. The method of claim 5, wherein a respective unit-length random vector includes vector elements with a magnitude less than or equal to a predetermined upper bound.

7. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

receiving a user-ratings snapshot, wherein the user-ratings snapshot comprises a first group identifier for a first end-user and a first ratings vector for the first end-user, and wherein the ratings vector indicates a rating value for each of a plurality of rated items;

associating the first ratings vector to a ratings group identified by the first group identifier;

receiving a recommendation request indicating a second group identifier for a second end-user, wherein the second group identifier identifies the ratings group;

determining a plurality of ratings vectors associated with the ratings group; and

generating a recommendation based on the plurality of ratings vectors, wherein generating the recommendation involves;

determining, from the plurality of ratings vectors, a corresponding plurality of standardized ratings for a rated item of one or more rated items, wherein a standardized rating from a respective end-user is standardized based on a rating average for the respective end-user;

computing a standardized average rating for the rated item by computing the average for the plurality of standardized ratings;

computing an average rating for the rated item by adding the second end-user'"'"'s average rating to the standardized average rating; and

selecting an item that has the highest average rating among the one or more rated items.

8. The storage medium of claim 7, wherein the ratings group is identified by a plurality of encrypted group identifiers,

wherein the first and second group identifiers each comprise a group identifier which has been encrypted using a shared key corresponding to the first and second users, and

wherein the method further comprises determining that the second end-user is associated with the ratings group by determining that the second group identifier matches at least the first group identifier.

9. The storage medium of claim 7, further comprising:

responsive to determining that the first group identifier for the first end-user does not match a group identifier of an existing ratings group;

creating a ratings group corresponding to the first group identifier; and

associating the ratings group with the first group identifier.

10. The storage medium of claim 7, further comprising:

generating a group-identifying hash function; and

sending the group-identifying hash function to a plurality of entities.

11. The storage medium of claim 10, wherein generating the group-identifying hash function involves:

generating a set of k random vectors, wherein a respective vector includes m random values, and wherein the respective random vector is orthogonal to other random vectors in the set;

normalizing the random vectors in the set to produce unit-length random vectors; and

generating the group-identifying hash function based on the set of k unit-length random vectors, wherein the group-identifying hash function maps an m-dimensional ratings vector into a k-bit string.

12. The storage medium of claim 11, wherein a respective unit-length random vector includes vector elements with a magnitude less than or equal to a predetermined upper bound.

13. An apparatus comprising:

a processor;

a memory;

a communication module to receive a user-ratings snapshot, wherein the user-ratings snapshot comprises a first group identifier for a first end-user and a first ratings vector for the first end-user, and wherein the ratings vector indicates a rating value for each of a plurality of rated items;

a group-identifying module to associate the first ratings vector to a ratings group identified by the first group identifier; and

a recommendation module to generate a recommendation based on the ratings group,

wherein the communication module is further configured to receive a recommendation request indicating a second group identifier for a second end-user, wherein the second group identifier identifies the ratings group, and

wherein the recommendation module is further configured to;

determine a plurality of ratings vectors associated with the ratings group; and

generate a recommendation based on the plurality of ratings vectors, and

wherein while generating the recommendation, the recommendation module is further configured to;

determine, from the plurality of ratings vectors, a corresponding plurality of standardized ratings for a rated item of one or more rated items, wherein a standardized rating from a respective end-user is standardized based on a rating average for the respective end-user;

compute a standardized average rating for the rated item by computing the average for the plurality of standardized ratings;

compute an average rating for the rated item by adding the second end-user'"'"'s average rating to the standardized average rating; and

select an item that has the highest average rating among the one or more rated items.

14. The apparatus of claim 13, wherein the ratings group is identified by a plurality of encrypted group identifiers,

wherein the first and second group identifiers each comprise a group identifier which has been encrypted using a shared key corresponding to the first and second users, and

wherein the group-identifying module is further configured to determine that the second end-user is associated with the ratings group by determining that the second group identifier matches at least the first group identifier.

15. The apparatus of claim 13, wherein responsive to determining that the first group identifier for the first end-user does not match a group identifier of an existing ratings group, the group-identifying module is further configured to:

create a ratings group corresponding to the first group identifier; and

associate the ratings group with the first group identifier.

16. The apparatus of claim 13, wherein the recommendation module is further configured to:

generate a group-identifying hash function; and

send the group-identifying hash function to a plurality of entities.

17. The apparatus of claim 16, wherein while generating the group-identifying hash function the recommendation module is further configured to:

generate a set of k random vectors, wherein a respective vector includes m random values, and wherein the respective random vector is orthogonal to other random vectors in the set;

normalize the random vectors in the set to produce unit-length random vectors; and

generate the group-identifying hash function based on the set of k unit-length random vectors, wherein the group-identifying hash function maps an m-dimensional ratings vector into a k-bit string.

18. The apparatus of claim 17, wherein a respective random vector includes vector elements with a magnitude less than or equal to a predetermined upper bound.