Scalable user clustering based on set similarity

• US 7,739,314 B2
• Filed: 08/15/2005
• Issued: 06/15/2010
• Est. Priority Date: 08/15/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Datar, Mayur, Garg, Ashutosh
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Hotelling; Harold A
• Application Number:
  US11/204,922
• Publication Number:
  US 20070038659A1
• Time in Patent Office: 1,765 Days
• Field of Search: None
• US Class Current: 707/803
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Methods and apparatus, including systems and computer program products, to provide clustering of users in which users are each represented as a set of elements representing items, e.g., items selected by users using a system. In one aspect, a program operates to obtain a respective interest set for each of multiple users, each interest set representing items in which the respective user expressed interest; for each of the users, to determine k hash values of the respective interest set, wherein the i-th hash value is a minimum value under a corresponding i-th hash function; and to assign each of the multiple users to each of the respective k clusters established for the respective user, the i-th cluster being represented by the i-th hash value. The assignment of each of the users to k clusters is done without regard to the assignment of any of the other users to k clusters.

Claims

1. A computer program product, encoded on a machine-readable storage device, comprising instructions that when executed by a processor cause a data processing apparatus to:

obtain a respective interest set for each of multiple users, each interest set being a set of elements, each element representing a respective item in which the respective user has expressed interest through interaction with a data processing system;

for each of the multiple users, apply an i-th hash function to each element of the interest set of the user to obtain a respective function value corresponding to the respective element, for each integer i between 1 and k, the k hash functions being distinct each from the others, and determine, from the function values obtained from the k hash functions, k hash values of the respective interest set, wherein the i-th hash value of the respective interest set is a minimum value among the function values obtained by applying the i-th hash function to the elements of interest set of the user, and where k is an integer greater than or equal to 1; and

assign each of the multiple users to each of k clusters, the i-th cluster being represented by the i-th hash value of the respective interest set of the respective user, wherein the assignment of each of the multiple users to k clusters is done without regard to the assignment of any of the other users to k clusters.

2. The product of claim 1, further comprising instructions that when executed by a processor cause a data processing apparatus to:

record actions expressing user interest in a log; and

use the log to generate the interest sets for the multiple users.

3. The product of claim 1, further comprising instructions that when executed by a processor cause a data processing apparatus to:

obtain a changed interest set for a first user of the multiple users;

determine k hash values for the first user using the changed interest set; and

assign the first user only to each of the respective k clusters represented by the k hash values determined using the changed interest set without changing the assignment of any the other multiple users to clusters.

4. The product of claim 1, where k is greater than 1.

5. The computer program product of claim 1, wherein the instructions further cause a data processing apparatus to:

execute a collaborative filtering computer program application to provide information to a first user of the multiple users based on the assignment of the first user to one or more of the k clusters.

6. A computer program product, encoded on a machine-readable storage device, comprising instructions that when executed by a processor cause a data processing apparatus to:

obtain an interest set for a user, the interest set being a set of elements, each element representing a respective item in which the user has expressed interest through interaction with a data processing system;

apply an i-th hash function to each element of the interest set to obtain a respective function value corresponding to the respective element, for each integer i between 1 and k, the k hash functions being distinct each from the others, and determine, from the function values obtained from the k hash functions, k hash values of the interest set, wherein the i-th hash value is a minimum value among the function values obtained by applying the i-th hash function to the elements of interest set of the user, where k is an integer greater than or equal to 1; and

assign the user to each of k clusters, the i-th cluster being represented by the i-th hash value.

7. The product of claim 6, wherein:

the interest set has m elements;

the i-th hash value is a minimum value of m applications of a one-way hash function,

each application hashing an i-th seed value and a respective one of the m elements of the interest set.

8. The product of claim 6, further comprising instructions that when executed by a processor cause a data processing apparatus to:

use the k user clusters to perform collaborative filtering for the user.

9. A system, comprising:

one or more machine-readable storage media storing a log of items selected by multiple users using a data processing system, the log of items identifying, for each of the multiple users, multiple items that the respective user has selected through interaction with the data processing system;

one or more computers configured to use the log to generate a respective interest set for each of the multiple users, each interest set being a set of elements, each element representing a respective item in which the respective user has selected through interaction with the data processing system;

one or more computers configured to apply, for each of the multiple users, an i-th hash function to each element of the interest set of the user to obtain a respective function value corresponding to the respective element, for each integer i between 1 and k, the k hash functions being distinct each from the others, and to determine, from the function values obtained from the k hash functions, k hash values of the respective interest set, wherein the i-th hash value of the respective interest set is a minimum value among the function values obtained by applying the i-th hash function to the elements of interest set of the user, and where k is an integer greater than or equal to 1;

one or more computers configured to assign each of the multiple users to each of k clusters, the i-th cluster being represented by the i-th hash value of the respective interest set of the respective user, wherein the assignment of each of the multiple users to k clusters is done without regard to the assignment of any of the other users to k clusters; and

one or more computers configured to execute a collaborative filtering computer program application to provide information to a first user of the multiple users based on the assignment of the first user to one or more of the k clusters.

10. The system of claim 9, wherein the information comprises at least one of a recommendation, a prediction, or a ranking.

11. The system of claim 9, wherein k is between 5 and 10, inclusive.

12. The system of claim 9, further comprising one or more computers configured to:

apply the fingerprint function the interest sets to generate k sets of hash values, and

select, as the respective k fingerprint values, a minimum value from each set of hash values.

13. A computer-implemented method comprising:

obtaining a respective interest set for each of multiple users, each interest set being a set of elements, each element representing a respective item in which the respective user has expressed interest through interaction with a data processing system;

for each of the multiple users, applying an i-th hash function to each element of the interest set of the user to obtain a respective function value corresponding to the respective element, for each integer i between 1 and k, the k hash functions being distinct each from the others, and determining, from the function values obtained from the k hash functions, k hash values of the respective interest set, wherein the i-th hash value of the respective interest set is a minimum value among the function values obtained by applying the i-th hash function to the elements of interest set of the user, where k is an integer greater than or equal to 1; and

assigning each of the multiple users to each of k clusters established for the respective user, the i-th cluster being represented by the i-th hash value of the respective interest set of the respective user, wherein the assignment of each of the multiple users to k clusters is done without regard to the assignment of any of the other users to k clusters.

14. The method of claim 13, further comprising:

recording actions expressing user interest in a log; and

using the log to generate the interest sets for the multiple users.

15. The method of claim 13, where k is greater than 1.

16. The method of claim 13, further comprising executing a collaborative filtering computer program application to provide information to a first user of the multiple users based on the assignment of the first user to one or more of the k clusters.

17. The method of claim 13, further comprising:

obtaining a changed interest set for a first user of the multiple users;

determining k hash values for the first user using the changed interest set; and

assigning the first user only to each of the respective k clusters represented by the k hash values determined using the changed interest set without changing the assignment of any the other multiple users to clusters.

18. A computer-implemented method comprising:

obtaining an interest set for a user, the interest set being a set of elements, each element representing a respective item in which the user has expressed interest through interaction with a data processing system;

applying an i-th hash function to each element of the interest set to obtain a respective function value corresponding to the respective element, for each integer i between 1 and k, the k hash functions being distinct each from the others, and determining, from the function values obtained from the k hash functions, k hash values of the interest set, wherein the i-th hash value is a minimum value among the function values obtained by applying the i-th hash function to the elements of interest set of the user, where k is an integer greater than or equal to 1; and

assigning the user to each of k clusters, the i-th cluster being represented by the i-th hash value.

19. The method of claim 18, wherein:

the interest set has m elements;

the i-th hash value is a minimum value of m applications of a one-way hash function, each application hashing an i-th seed value and a respective one of the m elements of the interest set.

20. The method of claim 18, further comprising:

using the k user clusters to perform collaborative filtering for the user.

21. The method of claim 18, further comprising:

recording actions expressing user interest in a log; and

using the log to generate the interest set for the user.

22. A system comprising:

one or more computers; and

a machine-readable storage medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

obtaining an interest set for a user, the interest set being a set of elements, each element representing a respective item in which the user has expressed interest through interaction with a data processing system;

applying an i-th hash function to each element of the interest set to obtain a respective function value corresponding to the respective element, for each integer i between 1 and k, the k hash functions being distinct each from the others, and determine, from the function values obtained from the k hash functions, k hash values of the interest set, wherein the i-th hash value is a minimum value among the function values obtained by applying the i-th hash function to the elements of interest set of the user, where k is an integer greater than or equal to 1; and

assigning the user to each of k clusters, the i-th cluster being represented by the i-th hash value.

23. The system of claim 22, wherein the operations further comprise:

recording actions expressing user interest in a log; and

using the log to generate the interest set for the user.

24. The system of claim 22, wherein:

the interest set has m elements;

the i-th hash value is a minimum value of m applications of a one-way hash function,

each application hashing an i-th seed value and a respective one of the m elements of the interest set.

25. The system of claim 22, wherein the operations further comprise:

using the k user clusters to perform collaborative filtering for the user.

26. A system comprising:

one or more computers; and

a machine-readable storage medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

obtaining a respective interest set for each of multiple users, each interest set being a set of elements, each element representing a respective item in which the respective user has expressed interest through interaction with a data processing system;

for each of the multiple users, applying an i-th hash function to each element of the interest set of the user to obtain a respective function value corresponding to the respective element, for each integer i between 1 and k, the k hash functions being distinct each from the others, and determine, from the function values obtained from the k hash functions, k hash values of the respective interest set, wherein the i-th hash value of the respective interest set is a minimum value among the function values obtained by applying the i-th hash function to the elements of interest set of the user, and where k is an integer greater than or equal to 1; and

assigning each of the multiple users to each of k clusters, the i-th cluster being represented by the i-th hash value of the respective interest set of the respective user, wherein the assignment of each of the multiple users to k clusters is done without regard to the assignment of any of the other users to k clusters.

27. The system of claim 26, wherein the operations further comprise:

recording actions expressing user interest in a log; and

using the log to generate the interest sets for the multiple users.

28. The system of claim 26, wherein the operations further comprise:

obtaining a changed interest set for a first user of the multiple users;

determining k hash values for the first user using the changed interest set; and

assigning the first user only to each of the respective k clusters represented by the k hash values determined using the changed interest set without changing the assignment of any the other multiple users to clusters.

29. The system of claim 26, where k is greater than 1.

30. A computer program product, encoded on a machine-readable storage device, comprising instructions that when executed by a processor cause a data processing apparatus to:

store a log of items selected by multiple users using a data processing system, the log of items identifying, for each of the multiple users, multiple items that the respective user has selected through interaction with the data processing system;

one or more computers configured to use the log to generate a respective interest set for each of the multiple users, each interest set being a set of elements, each element representing a respective item in which the respective user has selected through interaction with the data processing system;

one or more computers configured to apply, for each of the multiple users, an i-th hash function to each element of the interest set of the user to obtain a respective function value corresponding to the respective element, for each integer i between 1 and k, the k hash functions being distinct each from the others, and to determine, from the function values obtained from the k hash functions, k hash values of the respective interest set, wherein the i-th hash value of the respective interest set is a minimum value among the function values obtained by applying the i-th hash function to the elements of interest set of the user, and where k is an integer greater than or equal to 1;

one or more computers configured to assign each of the multiple users to each of k clusters, the i-th cluster being represented by the i-th hash value of the respective interest set of the respective user, wherein the assignment of each of the multiple users to k clusters is done without regard to the assignment of any of the other users to k clusters; and

one or more computers configured to execute a collaborative filtering computer program application to provide information to a first user of the multiple users based on the assignment of the first user to one or more of the k clusters.

31. The computer program product of claim 30, wherein the information comprises at least one of a recommendation, a prediction, or a ranking

32. The computer program product of claim 30, wherein k is between 5 and 10, inclusive.

33. The computer program product of claim 30, wherein the instructions further cause a data processing apparatus to:

apply the fingerprint function the interest sets to generate k sets of hash values, and

select, as the respective k fingerprint values, a minimum value from each set of hash values.