Scalable user clustering based on set similarity

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.

1 . A computer-implemented method comprising:
 assigning each of multiple users to multiple clusters based on items that each respective user has selected;   determining that a cluster assignment for a particular user is to be updated; and   in response to determining that the cluster assignment for the particular user is to be updated, updating an assignment of the particular user to the multiple clusters, without affecting an assignment of any other of the multiple users to the multiple clusters.   
     
     
         2 . The method of  claim 1 , wherein each of the multiple users are assigned to the multiple clusters in isolation, independent of an assignment of any other of the multiple users to the multiple clusters. 
     
     
         3 . The method of  claim 1 , wherein:
 determining that a cluster assignment for a particular user is to be updated comprises determining that the particular user is to be added.   
     
     
         4 . The method of  claim 3 , wherein:
 determining that the particular user is to be added comprises determining that the particular user has expressed that the items that the particular user has selected are to be disclosed.   
     
     
         5 . The method of  claim 1 , wherein:
 determining that a cluster assignment for a particular user is to be updated comprises determining that the particular user is to be deleted.   
     
     
         6 . The method of  claim 5 , wherein:
 determining that the particular user is to be deleted comprises determining that the user is a spam user.   
     
     
         7 . The method of  claim 5 , wherein:
 determining that the particular user is to be deleted comprises determining that the user has expressed sham interest.   
     
     
         8 . The method of  claim 1 , wherein determining that a cluster assignment for a particular user is to be updated comprises determining that the particular user has edited the items that the particular user has selected. 
     
     
         9 . The method of  claim 1 , wherein updating an assignment of the particular user to the multiple clusters comprises updating an assignment of the particular user only, without updating an assignment of any other of the multiple users. 
     
     
         10 . A system comprising:
 one or more computers and one or more storage devices storing instructions that are operable, upon execution by the one or more computers, to cause the one or more computers to perform operations comprising:   assigning each of multiple users to multiple clusters based on items that each respective user has selected;   determining that a cluster assignment for a particular user is to be updated; and   in response to determining that the cluster assignment for the particular user is to be updated, updating an assignment of the particular user to the multiple clusters, without affecting an assignment of any other of the multiple users to the multiple clusters.   
     
     
         11 . The system of  claim 10 , wherein each of the multiple users are assigned to the multiple clusters in isolation, independent of an assignment of any other of the multiple users to the multiple clusters. 
     
     
         12 . The system of  claim 10 , wherein:
 determining that a cluster assignment for a particular user is to be updated comprises determining that the particular user is to be added.   
     
     
         13 . The system of  claim 12 , wherein:
 determining that the particular user is to be added comprises determining that the particular user has expressed that the items that the particular user has selected are to be disclosed.   
     
     
         14 . The system of  claim 10 , wherein:
 determining that a cluster assignment for a particular user is to be updated comprises determining that the particular user is to be deleted.   
     
     
         15 . The system of  claim 14 , wherein:
 determining that the particular user is to be deleted comprises determining that the user is a spam user.   
     
     
         16 . The system of  claim 14 , wherein:
 determining that the particular user is to be deleted comprises determining that the user has expressed sham interest.   
     
     
         17 . The system of  claim 10 , wherein determining that a cluster assignment for a particular user is to be updated comprises determining that the particular user has edited the items that the particular user has selected. 
     
     
         18 . The system of  claim 10 , wherein updating an assignment of the particular user to the multiple clusters comprises updating an assignment of the particular user only, without updating an assignment of any other of the multiple users. 
     
     
         19 . A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:
 assigning each of multiple users to multiple clusters based on items that each respective user has selected;   determining that a cluster assignment for a particular user is to be updated; and   in response to determining that the cluster assignment for the particular user is to be updated, updating an assignment of the particular user to the multiple clusters, without affecting an assignment of any other of the multiple users to the multiple clusters.   
     
     
         20 . The medium of  claim 19 , wherein each of the multiple users are assigned to the multiple clusters in isolation, independent of an assignment of any other of the multiple users to the multiple clusters. 
     
     
         21 . The medium of  claim 19 , wherein:
 determining that a cluster assignment for a particular user is to be updated comprises determining that the particular user is to be added.   
     
     
         22 . The medium of  claim 21 , wherein:
 determining that the particular user is to be added comprises determining that the particular user has expressed that the items that the particular user has selected are to be disclosed.   
     
     
         23 . The medium of  claim 19 , wherein:
 determining that a cluster assignment for a particular user is to be updated comprises determining that the particular user is to be deleted.   
     
     
         24 . The medium of  claim 23 , wherein:
 determining that the particular user is to be deleted comprises determining that the user is a spam user.   
     
     
         25 . The medium of  claim 23 , wherein:
 determining that the particular user is to be deleted comprises determining that the user has expressed sham interest.   
     
     
         26 . The medium of  claim 19 , wherein determining that a cluster assignment for a particular user is to be updated comprises determining that the particular user has edited the items that the particular user has selected. 
     
     
         27 . The medium of  claim 19 , wherein updating an assignment of the particular user to the multiple clusters comprises updating an assignment of the particular user only, without updating an assignment of any other of the multiple users.