Inferring Geographic Locations for Entities Appearing in Search Queries

Abstract

A server system associates one or more locations with a query by identifying the query, selecting a set of documents responsive to the query, and assigning weights to respective documents in the set of documents based, at least in part, on historical data of user clicks selecting search result links in search results produced for historical queries substantially the same as the identified query. Websites hosting the selected documents are identified, and, for each website, location-specific information for one or more locations is retrieved, including a location-specific score that corresponds to the likelihood that the respective location corresponds to a respective website. For each respective location for which location-specific information was retrieved, aggregating the location-specific scores, as weighted by the document weights, to compute an aggregated likelihood that the respective location is associated with the query. A specific location is assigned to the query when predefined criteria are satisfied.

1 . A method for inferring locations associated with a website, performed by a server system having one or more processors and memory storing one or more programs for execution by the one or more processors, the method comprising:
 at the server system:   identifying a website;   for each respective location of a plurality of locations referenced in queries with respective result sets that comprise search result links to documents hosted at the website, computing a location-specific score representing the likelihood that the respective location is associated with the website;   computing a site confidence value representing a likelihood that the website is associated with a physical location;   determining a location associated with the website using the location-specific scores and the site confidence value;   storing information indicating that the determined location is associated with the website for subsequent use when processing respective search queries.   
     
     
         2 . The method of  claim 1 , further including:
 processing a received search query from a client device or system to produce a set of search results, at least one of which comprises a search result link to a document hosted at the website; and   returning to the client device or system at least a subset of the set of search results and information identifying the determined location.   
     
     
         3 . The method of  claim 1 , further comprising:
 computing, with respect to the queries with respective result sets that comprise search result links to documents hosted at the website, a site click count that provides a total number of clicks that select search result links to documents hosted at the website;   computing, for the website, a location-referencing click count that provides a number of said clicks that select search result links provided in the result sets of respective queries that reference any of a plurality of locations; and   for each respective location of the plurality of locations, computing a location-specific click count that provides a number of said clicks that select search result links provided in the result sets of respective queries that reference the respective location;   wherein:   computing the location-specific score is performed in accordance with the location-referencing click count and the location-specific click count for the respective location; and   computing the confidence value is performed in accordance with the site click count and location-referencing click count.   
     
     
         4 . The method of  claim 3 , wherein computing the location-specific score comprises dividing the location-specific click count by the location-referencing click count. 
     
     
         5 . The method of  claim 3 , wherein computing the confidence value comprises dividing the location-referencing click count by the site click count. 
     
     
         6 . The method of  claim 1 , wherein the plurality of locations referenced in queries with respective result sets that comprise search result links to documents hosted at the website comprise locations explicitly or implicitly referenced by terms in the queries. 
     
     
         7 . The method of  claim 1 , wherein determining a location associated with the website using the location-specific scores and the site confidence value includes, for at least one of the location-specific score, combining the location-specific score with the site confidence value to produce a location-specific confidence value for a corresponding location, determine if the location-specific confidence value exceeds a predefined threshold value, and associating the location corresponding to the location-specific confidence value with the website when location-specific confidence value exceeds the predefined threshold value. 
     
     
         8 . The method of  claim 1 , wherein each document hosted at the website has a web address, the web address including an initial portion that is in common with the web address of other documents hosted at the website. 
     
     
         9 . The method of  claim 8 , wherein the initial portion of the web addresses comprises a domain name or a domain name in combination with a subdirectory. 
     
     
         10 . A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer system having one or more processors and memory storing one or more programs for execution by the one or more processors, the one or more programs comprising instructions for:
 identifying a website;   for each respective location of a plurality of locations referenced in queries with respective result sets that comprise search result links to documents hosted at the website, computing a location-specific score representing the likelihood that the respective location is associated with the website;   computing a site confidence value representing a likelihood that the website is associated with a physical location;   determining a location associated with the website using the location-specific scores and the site confidence value;   storing information indicating that the determined location is associated with the website for subsequent use when processing respective search queries.   
     
     
         11 . The non-transitory computer readable storage medium of  claim 10 , wherein the one or more programs further comprise instructions for:
 processing a received search query from a client device or system to produce a set of search results, at least one of which comprises a search result link to a document hosted at the website; and   returning to the client device or system at least a subset of the set of search results and information identifying the determined location.   
     
     
         12 . A server computer system comprising:
 one or more processors; and   memory storing one or more programs for execution by the one or more processors, the one or more programs comprising instructions for:   identifying a website;   for each respective location of a plurality of locations referenced in queries with respective result sets that comprise search result links to documents hosted at the website, computing a location-specific score representing the likelihood that the respective location is associated with the website;   computing a site confidence value representing a likelihood that the website is associated with a physical location;   determining a location associated with the website using the location-specific scores and the site confidence value;   storing information indicating that the determined location is associated with the website for subsequent use when processing respective search queries.   
     
     
         13 . The server computer system of  claim 12 , wherein the one or more programs comprise instructions for:
 processing a received search query from a client device or system to produce a set of search results, at least one of which comprises a search result link to a document hosted at the website; and   returning to the client device or system at least a subset of the set of search results and information identifying the determined location.   
     
     
         14 . A method for assigning a location to a query, performed by a server system having one or more processors and memory storing one or more programs for execution by the one or more processors, the method comprising:
 at the server system:   identifying a query;   selecting a set of documents responsive to the identified query;   assigning weights to respective documents in the set of documents based, at least in part, on historical data of user clicks selecting search result links in search results produced for historical queries substantially the same as the identified query;   identifying respective websites hosting the documents in the set of documents;   for each website of a plurality of the identified websites, retrieving location-specific information for one or more locations, the retrieved information for a respective location comprising a location-specific score that corresponds to the likelihood that the respective location corresponds to a respective website of the identified websites;   for each respective location for which location-specific information was retrieved, aggregating the location-specific scores, as weighted by the document weights, to compute an aggregated likelihood that the respective location is associated with the query; and   assigning a specific location to the query when predefined criteria are satisfied, the predefined criteria comprising a requirement that the aggregated likelihood for the specific location exceeds a first predefined value.   
     
     
         15 . The method of  claim 14 , wherein:
 the information retrieved for each website of the plurality of identified websites further comprises a website confidence value for the website that corresponds to a likelihood that at least one physical location corresponds to the website;   the method further comprises aggregating the website confidence values as weighted by the document weights to compute an aggregated confidence value for the query; and   the predefined criteria further comprises a requirement that the aggregated confidence value for the query exceeds a second predefined value.   
     
     
         16 . The method of  claim 14 , wherein
 the information retrieved for each website of the plurality of identified websites further comprises a website confidence value for the website, the website confidence value corresponding to a likelihood that at least one physical location corresponds to the website;   the aggregated likelihood comprises a location-specific query score, query_score(Q,l) for the identified query Q and the respective location l, and is computed by aggregating the location-specific scores weighted by both the document weights and the website confidence values.   
     
     
         17 . The method of  claim 16 , wherein the location-specific query score, query_score(Q,l) for the identified query Q and the respective location l, and is computed in accordance with a predefined summation equation comprising: 
       
         
           
             
               
                 
                   query_score 
                    
                   
                     ( 
                     
                       Q 
                       , 
                       l 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     ∑ 
                     
                       d 
                       ∈ 
                       
                         re 
                          
                         
                           ( 
                           Q 
                           ) 
                         
                       
                     
                   
                    
                   
                     
                       
                         weight 
                          
                         
                           ( 
                           
                             d 
                             , 
                             Q 
                           
                           ) 
                         
                       
                       · 
                       site_conf 
                     
                      
                     
                       
                         ( 
                         
                           site 
                            
                           
                             ( 
                             d 
                             ) 
                           
                         
                         ) 
                       
                       · 
                       I 
                     
                      
                     
                         
                     
                      
                     s 
                      
                     
                         
                     
                      
                     
                       s 
                        
                       
                         ( 
                         
                           
                             site 
                              
                             
                               ( 
                               d 
                               ) 
                             
                           
                           , 
                           l 
                         
                         ) 
                       
                     
                   
                 
               
               , 
             
           
         
       
       where site(d) is the website that hosts document d, lss(site(d),l) is the retrieved location-specific score for the website that hosts document d, site_conf(site(d)) is the site confidence score for the website that hosts document d, and the summation is performed with respect to documents in the selected set of documents responsive to the identified query. 
     
     
         18 . The method of  claim 14 , wherein the identified query is received from a client device or system, the method further comprising:
 returning to the client device or system at least a subset of the documents responsive to the received query and information identifying or corresponding to the specific location assigned to the query.   
     
     
         19 . The method of  claim 14 , further comprising:
 storing the identified query and the corresponding assigned specific location in a repository;   receiving a new query from a client device or system;   matching the new query to the identified query; and   returning to the client device or system a set of search results for the new query and information identifying or corresponding to the specific location assigned to the query   
     
     
         20 . The method of  claim 19 , further comprising converting the identified query to a canonical form prior to storing in the repository and converting the new query to a canonical form prior to matching the new query to the identified query. 
     
     
         21 . A server system, comprising:
 one or more processors; and   memory storing one or more programs for execution by the one or more processors, the one or more programs comprising instructions for:   identifying a query;   selecting a set of documents responsive to the identified query;   assigning weights to respective documents in the set of documents based, at least in part, on historical data of user clicks selecting search result links in search results produced for historical queries substantially the same as the identified query;   identifying respective websites hosting the documents in the set of documents;   for each website of a plurality of the identified websites, retrieving location-specific information for one or more locations, the retrieved information for a respective location comprising a location-specific score that corresponds to the likelihood that the respective location corresponds to a respective website of the identified websites;   for each respective location for which location-specific information was retrieved, aggregating the location-specific scores, as weighted by the document weights, to compute an aggregated likelihood that the respective location is associated with the query; and   assigning a specific location to the query when predefined criteria are satisfied, the predefined criteria comprising a requirement that the aggregated likelihood for the specific location exceeds a first predefined value.   
     
     
         22 . The server system of  claim 21 , wherein
 the information retrieved for each website of the plurality of identified websites further comprises a website confidence value for the website that corresponds to a likelihood that at least one physical location corresponds to the website;   the method further comprises aggregating the website confidence values as weighted by the document weights to compute an aggregated confidence value for the query; and   the predefined criteria further comprises a requirement that the aggregated confidence value for the query exceeds a second predefined value.   
     
     
         23 . A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer system having one or more processors and memory storing one or more programs for execution by the one or more processors, the one or more programs comprising instructions for:
 identifying a query;   selecting a set of documents responsive to the identified query;   assigning weights to respective documents in the set of documents based, at least in part, on historical data of user clicks selecting search result links in search results produced for historical queries substantially the same as the identified query;   identifying respective websites hosting the documents in the set of documents;   for each website of a plurality of the identified websites, retrieving location-specific information for one or more locations, the retrieved information for a respective location comprising a location-specific score that corresponds to the likelihood that the respective location corresponds to a respective website of the identified websites;   for each respective location for which location-specific information was retrieved, aggregating the location-specific scores, as weighted by the document weights, to compute an aggregated likelihood that the respective location is associated with the query; and   assigning a specific location to the query when predefined criteria are satisfied, the predefined criteria comprising a requirement that the aggregated likelihood for the specific location exceeds a first predefined value.   
     
     
         24 . The non-transitory computer readable storage medium of  claim 23 , wherein
 the information retrieved for each website of the plurality of identified websites further comprises a website confidence value for the website that corresponds to a likelihood that at least one physical location corresponds to the website;   the method further comprises aggregating the website confidence values as weighted by the document weights to compute an aggregated confidence value for the query; and   the predefined criteria further comprises a requirement that the aggregated confidence value for the query exceeds a second predefined value.