Anonymous crowd comparison

Abstract

Systems and methods are disclosed for anonymously comparing user groups, such as but not limited to crowds, to determine a degree of user overlap. In general, a hash value is obtained for a first user group, where the hash value includes a hash value component for a number of two-user permutations within the first user group. Similarly, a hash value is obtained for a second user group, where the hash value includes a hash value component for a number of two-user permutations within the second user group. Thereafter, a degree of user overlap between the first and second user groups is determined based on a comparison of the hash value for the first user group and the hash value for the second user group.

What is claimed is: 
     
         1 . A computer-implemented method comprising:
 obtaining a hash value for a first user group, the hash value for the first user group comprising a plurality of component hash values generated for a plurality of two-user permutations for the first user group;   obtaining a hash value for a second user group, the hash value for the second user group comprising a plurality of component hash values generated for a plurality of two-user permutations for the second user group; and   determining a degree of user overlap between the first user group and the second user group based on a comparison of the hash value for the first user group and the hash value for the second user group.   
     
     
         2 . The method of  claim 1  wherein:
 the plurality of two user-permutations for the first user group comprises all distinct two-user permutations for the first user group, and each of the plurality of component hash values for the first user group is a hash value computed for a corresponding one of the plurality of two-user permutations for the first user group based on a predetermined hash function; and 
 the plurality of two user-permutations for the second user group comprises all distinct two-user permutations for the second user group, and each of the plurality of component hash values for the second user group is a hash value computed for a corresponding one of the plurality of two-user permutations for the second user group based on the predetermined hash function. 
 
     
     
         3 . The method of  claim 1  wherein:
 the plurality of two user-permutations for the first user group comprises all distinct two-user permutations for the first user group other than those that include a requesting user associated with the hash value for the first user group, and each of the plurality of component hash values for the first user group is a hash value computed for a corresponding one of the plurality of two-user permutations for the first user group based on a predetermined hash function; and 
 the plurality of two user-permutations for the second user group comprises all distinct two-user permutations for the second user group other than those that include a requesting user associated with the hash value for the second user group, and each of the plurality of component hash values for the second user group is a hash value computed for a corresponding one of the plurality of two-user permutations for the second user group based on the predetermined hash function. 
 
     
     
         4 . The method of  claim 1  wherein obtaining the hash value for the first user group comprises:
 obtaining a list of users in the first user group; 
 removing a requesting user that initiated a process for obtaining the hash value for the first user group from the list of users; 
 sorting the list of users in the first user group to provide a sorted list of users; 
 creating the plurality of two-user permutations for the first user group from the sorted list of users; 
 computing a component hash value for each of the plurality of two-user permutations for the first user group to provide the plurality of component hash values for the first user group; and 
 concatenating the plurality of component hash values to provide a concatenated hash value for the first user group. 
 
     
     
         5 . The method of  claim 4  wherein obtaining the hash value for the first user group further comprises compressing the concatenated hash value for the first user group using a lossy compression algorithm to provide the hash value for the first user group. 
     
     
         6 . The method of  claim 5  wherein compressing the concatenated hash value comprises removing every Nth bit, where N is greater than or equal to 2. 
     
     
         7 . The method of  claim 5  wherein compressing the concatenated hash value comprises removing every other bit. 
     
     
         8 . The method of  claim 4  wherein sorting the list of users in the first user group to provide the sorted list of users is such that the plurality of two-user permutations for the first user group are canonical with respect to other instances of the plurality of two-user permutations for other user groups including the second user group. 
     
     
         9 . The method of  claim 1  wherein obtaining the hash value for the first user group comprises:
 obtaining a list of users in the first user group; 
 sorting the list of users in the first user group to provide a sorted list of users; 
 creating the plurality of two-user permutations for the first user group from the sorted list of users; 
 computing a component hash value for each of the plurality of two-user permutations for the first user group to provide the plurality of component hash values for the first user group; and 
 concatenating the plurality of component hash values to provide a concatenated hash value for the first user group. 
 
     
     
         10 . The method of  claim 9  wherein obtaining the hash value for the first user group further comprises compressing the concatenated hash value for the first user group using a lossy compression algorithm to provide the hash value for the first user group. 
     
     
         11 . The method of  claim 10  wherein compressing the concatenated hash value comprises removing every Nth bit, where N is greater than or equal to 2. 
     
     
         12 . The method of  claim 10  wherein compressing the concatenated hash value comprises removing every other bit. 
     
     
         13 . The method of  claim 9  wherein sorting the list of users in the first user group to provide the sorted list of users is such that the plurality of two-user permutations for the first user group are canonical with respect to other instances of the plurality of two-user permutations for other user groups including the second user group. 
     
     
         14 . The method of  claim 1  wherein determining the degree of user overlap between the first user group and the second user group comprises:
 determining a number of matching component hash values between the plurality of component hash values for the first user group and the plurality of component hash values for the second user group; and 
 determining a number of matching users in the first and second user groups based on the number of matching component hash values. 
 
     
     
         15 . The method of  claim 14  wherein the number of matching component hash values corresponds to a number of matching two-user permutations between the plurality of two-user permutations for the first user group and the plurality of two-user permutations for the second user group. 
     
     
         16 . The method of  claim 14  wherein determining the number of matching users in the first and second user groups based on the number of matching component hash values comprises determining the number of matching users in the first and second user groups based on: 
       
         
           
             
               
                 
                   
                     n 
                     ! 
                   
                   
                     
                       2 
                       ! 
                     
                      
                     
                       
                         ( 
                         
                           n 
                           - 
                           2 
                         
                         ) 
                       
                       ! 
                     
                   
                 
                 = 
                 
                   number_of 
                    
                   _matching 
                    
                   _two 
                    
                   _user 
                    
                   _permutations 
                 
               
               , 
             
           
         
       
       where number_of_matching_two_user_permutations is the number of matching component hash values and n is the number of matching users in the first and second user groups. 
     
     
         17 . The method of  claim 14  wherein determining the degree of user overlap between the first user group and the second user group further comprises:
 determining a largest user group of the first and second user groups; and 
 determining a percentage of user overlap based on a ratio of the number of matching users over a number of users in the largest user group of the first and second user groups. 
 
     
     
         18 . A server comprising:
 a communication interface communicatively coupling the server to a network; and   a controller associated with the communication interface and adapted to:
 obtain a hash value for a first user group, the hash value for the first user group comprising a plurality of component hash values generated for a plurality of two-user permutations for the first user group; 
 obtain a hash value for a second user group, the hash value for the second user group comprising a plurality of component hash values generated for a plurality of two-user permutations for the second user group; and 
 determine a degree of user overlap between the first user group and the second user group based on a comparison of the hash value for the first user group and the hash value for the second user group. 
   
     
     
         19 . A computer-readable medium storing software for instructing a controller to:
 obtain a hash value for a first user group, the hash value for the first user group comprising a plurality of component hash values generated for a plurality of two-user permutations for the first user group;   obtain a hash value for a second user group, the hash value for the second user group comprising a plurality of component hash values generated for a plurality of two-user permutations for the second user group; and   determine a degree of user overlap between the first user group and the second user group based on a comparison of the hash value for the first user group and the hash value for the second user group.   
     
     
         20 . A computer-implemented method comprising:
 receiving a crowd hash value storage request from a requestor;   obtaining a crowd in which the requestor is located at a time of receiving the crowd hash value storage request;   computing a crowd hash value for the crowd in which the requestor is located, the crowd hash value comprising a plurality of component hash values computed for a plurality of two-user permutations for the crowd in which the requestor is located; and   storing the crowd hash value as a crowd hash value for a crowd of interest of the requestor.   
     
     
         21 . The method of  claim 20  further comprising, at some time after storing the crowd hash value for the crowd of interest of the requestor:
 receiving a current crowd comparison request from the requestor; 
 obtaining a current crowd that is relevant to the current crowd comparison request; 
 computing a crowd hash value for the current crowd, the crowd hash value for the current crowd comprising a plurality of component hash values computed for a plurality of two-user permutations for the current crowd; 
 obtaining the crowd hash value of the crowd of interest of the requestor from storage; 
 determining a degree of user overlap between the current crowd and the crowd of interest of the requestor based on a comparison of the hash value for the current crowd and the hash value for the crowd of interest of the requestor; and 
 returning the degree of user overlap between the current crowd and the crowd of interest of the requestor to the requestor. 
 
     
     
         22 . The method of  claim 20  further comprising, at some time after storing the crowd hash value for the crowd of interest of the requestor:
 receiving a Point of Interest (POI) recommendation request from a requestor; 
 obtaining a plurality of relevant POIs that are relevant to the POI recommendation request; 
 for each relevant POI of the plurality of relevant POIs:
 obtaining a current crowd at the relevant POI; 
 computing a crowd hash value for the current crowd at the relevant POI, the crowd hash value comprising a plurality of component hash values computed for a plurality of two-user permutations for the current crowd at the relevant POI; and 
 determining a degree of user overlap between the current crowd at the relevant POI and the crowd of interest of the requestor based on a comparison of the crowd hash value for the current crowd at the relevant POI and the crowd hash value for the crowd of interest of the requestor obtained from storage; 
 
 selecting one or more recommended POIs from the plurality of relevant POIs based on the degree of user overlap between each current crowd at the plurality of relevant POIs and the crowd of interest of the requestor; and 
 returning the one or more recommended POIs to the requestor. 
 
     
     
         23 . The method of  claim 20  further comprising, at some time after storing the crowd hash value for the crowd of interest of the requestor:
 receiving a historical crowd comparison request from the requestor; 
 obtaining one or more historical crowds that are relevant to the historical crowd comparison request; 
 obtaining the crowd hash value of the crowd of interest of the requestor from storage; 
 for each historical crowd of the one or more historical crowds:
 obtaining a crowd hash value for the historical crowd, the crowd hash value for the historical crowd being previously computed and stored and comprising a plurality of component hash values computed for a plurality of two-user permutations for the historical crowd; and 
 determining a degree of user overlap between the historical crowd and the crowd of interest of the requestor based on a comparison of the hash value for the historical crowd and the hash value for the crowd of interest of the requestor; and 
 
 returning, to the requestor, data reflecting the degree of user overlap between each of the one or more historical crowds and the crowd of interest of the requestor. 
 
     
     
         24 . The method of  claim 23  further comprising:
 combining the degrees of user overlap between the one or more historical crowds and the crowd of interest of the requestor to provide a combined degree of user overlap; 
 wherein returning the data comprises returning the combined degree of user overlap. 
 
     
     
         25 . The method of  claim 20  further comprising, at some time after storing the crowd hash value for the crowd of interest of the requestor:
 receiving a Point of Interest (POI) recommendation request from a requestor; 
 obtaining a plurality of relevant POIs that are relevant to the POI recommendation request; 
 for each relevant POI of the plurality of relevant POIs:
 obtaining one or more historical crowds at the relevant POI; 
 for each historical crowd of the one or more historical crowds at the relevant POI, computing a crowd hash value for the historical crowd at the relevant POI, the crowd hash value comprising a plurality of component hash values computed for a plurality of two-user permutations for the historical crowd at the relevant POI; and 
 for each historical crowd of the one or more historical crowds at the relevant POI, determining a degree of user overlap between the historical crowd at the relevant POI and the crowd of interest of the requestor based on a comparison of the crowd hash value for the historical crowd at the relevant POI and the crowd hash value for the crowd of interest of the requestor obtained from storage; 
 
 selecting one or more recommended POIs from the plurality of relevant POIs based on the degree of user overlap between each of the historical crowd at each of the plurality of relevant POIs and the crowd of interest of the requestor; and 
 returning the one or more recommended POIs to the requestor. 
 
     
     
         26 . A server comprising:
 a communication interface communicatively coupling the server to a network; and   a controller associated with the communication interface and adapted to:
 receive a crowd hash value storage request from a requestor via the communication interface; 
 obtain a crowd in which the requestor is located at a time of receiving the crowd hash value storage request; 
 compute a crowd hash value for the crowd in which the requestor is located, the crowd hash value comprising a plurality of component hash values computed for a plurality of two-user permutations for the crowd in which the requestor is located; and 
 store the crowd hash value as a crowd hash value for a crowd of interest of the requestor. 
   
     
     
         27 . A computer-readable medium storing software for instructing a controller of a computing device to:
 receive a crowd hash value storage request from a requestor;   obtain a crowd in which the requestor is located at a time of receiving the crowd hash value storage request;   compute a crowd hash value for the crowd in which the requestor is located, the crowd hash value comprising a plurality of component hash values computed for a plurality of two-user permutations for the crowd in which the requestor is located; and   store the crowd hash value as a crowd hash value for a crowd of interest of the requestor.   
     
     
         28 . A computer-implemented method comprising:
 receiving a request to monitor crowds at a Point of Interest (POI) from a requestor;   computing a plurality of crowd hash values for a plurality of crowds at the POI over time, wherein, for each crowd hash value of the plurality of crowd hash values, the crowd hash value comprises a plurality of component hash values computed for a plurality of two-user permutations for a corresponding one of the plurality of crowds at the POI over time;   comparing the plurality of crowd hash values for the plurality of crowds at the POI over time to one another to provide data characterizing crowd patterns at the POI; and   returning the data characterizing crowd patterns at the POI to the requestor.   
     
     
         29 . The method of  claim 28  wherein comparing the plurality of crowd hash values for the plurality of crowds at the POI over time to one another to provide the data characterizing crowd patterns at the POI comprises:
 identifying a subset of the plurality of crowds that were at the POI during a reoccurring time window; 
 determining a combined degree of user overlap for the subset of the plurality of crowds based on a subset of the plurality of crowd hash values computed for the subset of the plurality of crowds; and 
 including the combined degree of user overlap for the subset of the plurality of crowds in the data characterizing crowd patterns at the POI. 
 
     
     
         30 . The method of  claim 28  wherein comparing the plurality of crowd hash values for the plurality of crowds at the POI over time to one another to provide the data characterizing crowd patterns at the POI comprises:
 identifying a subset of the plurality of crowds that were at the POI during a reoccurring time window; 
 determining a degree of user overlap between each pair of crowds in the subset of the plurality of crowds that were at the POI during the reoccurring time window based on comparisons of crowd hash values in a subset of the plurality of crowd hash values for the subset of the plurality of crowds to one another; 
 combining the degrees of user overlap for the pairs of crowds in the subset of the plurality of crowds that were at the POI during the reoccurring time window to provide a combined degree of user overlap for the reoccurring time window; and 
 including the combined degree of user overlap for the reoccurring time window in the data characterizing crowd patterns at the POI. 
 
     
     
         31 . A server comprising:
 a communication interface communicatively coupling the server to a network; and   a controller associated with the communication interface and adapted to:
 receive a request, via the communication interface, to monitor crowds at a Point of Interest (POI); 
 compute a plurality of crowd hash values for a plurality of crowds at the POI over time, wherein, for each crowd hash value of the plurality of crowd hash values, the crowd hash value comprises a plurality of component hash values computed for a plurality of two-user permutations for a corresponding one of the plurality of crowds at the POI over time; 
 compare the plurality of crowd hash values for the plurality of crowds at the POI over time to one another to provide data characterizing crowd patterns at the POI; and 
 return the data characterizing crowd patterns at the POI to the requestor. 
   
     
     
         32 . A computer-readable medium storing software for instructing a controller of a computing device to:
 receive a request to monitor crowds at a Point of Interest (POI);   compute a plurality of crowd hash values for a plurality of crowds at the POI over time, wherein, for each crowd hash value of the plurality of crowd hash values, the crowd hash value comprises a plurality of component hash values computed for a plurality of two-user permutations for a corresponding one of the plurality of crowds at the POI over time;   compare the plurality of crowd hash values for the plurality of crowds at the POI over time to one another to provide data characterizing crowd patterns at the POI; and   return the data characterizing crowd patterns at the POI to the requestor.