Interpreting user queries based on nearby locations

• US 10,474,671 B2
• Filed: 05/08/2015
• Issued: 11/12/2019
• Est. Priority Date: 05/12/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Behzadi, Behshad, Grimsmo, Nils
• Primary Examiner(s): Mofiz, Apu M
• Assistant Examiner(s): Holland, Sheryl L
• Application Number:
  US14/707,669
• Publication Number:
  US 20150324425A1
• Time in Patent Office: 1,649 Days
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: H04L 2101/69 using geographic information, e.g. room number

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for receiving a query provided from a user device, and determining that the query is implicitly about some entity, and in response: obtaining an approximate location of the user device when the user device provided the query, obtaining a set of entities including one or more entities, each entity in the set of entities being associated with the approximate location, and determining that the query is implicitly about an entity in the set of entities, and in response: providing a revised query based on the query and the entity, the revised query explicitly referencing the entity.

Claims

1. A computer-implemented method executed by one or more processors, the method comprising:

receiving, by the one or more processors, a query provided from a user device, the query including one or more n-grams that each include one or more terms; and

determining, by the one or more processors, that the query is implicitly about some entity for which an explicit reference to is absent from the one or more terms of the query, and in response;

obtaining, by the one or more processors, an approximate location of the user device when the user device provided the query,

obtaining, by the one or more processors and based on the approximate location of the user device, a set of entities, wherein each entity in the set of entities is a named place with a particular name and at a particular location, and each entity in the set of entities is obtained based on the particular location of the entity being within a threshold distance of the approximate location, and

determining, by the one or more processors, that the query is implicitly about an entity in the set of entities, and in response;

providing, by the one or more processors, a revised query based on the query and the particular name of the entity, the revised query explicitly referencing the entity by the particular name of the entity;

wherein;

determining that the query is implicitly about the entity in the set of entities that was obtained based on the approximate location of the user device comprises, for each entity in the set of entities;

accessing an index that associates entities with entity types and associates entity types with n-grams, wherein each entity type specifies a particular category to which a plurality of particular entities belong, and for each entity type, the index specifies n-grams that are determined be correlated to the entity type, and wherein each of the n-grams determined be correlated to the entity type are not n-grams that explicitly reference the particular entities that belong to the category specified by the entity type;

determining an entity type of the entity based on the index; and

determining whether the n-grams of the query correlate to the entity type of the entity based on the n-grams of the query matching n-grams that are determined be correlated to the entity type as specified in the index;

for each entity associated with the entity type to which the n-grams of the query correlate, including the entity in the sub-set of entities; and

selecting the entity from the subset of entities, wherein the subset of entities includes at least two or more entities, the selecting comprising;

determining that each of the entities in the subset of entities have a common attribute, wherein the common attribute for each entity relates to a popularity of the entity; and

selecting the entity with a highest popularity among the entities based on the common attribute.

2. The method of claim 1, wherein the one or more types associated with the query are provided from an index that associates types to respective n-grams of queries.

3. The method of claim 1, wherein receiving a set of entities and determining that the query is implicitly about an entity in the set of entities are performed in response to determining that the approximate location is sufficiently fresh.

4. A system comprising:

a non-transitory data store for storing data; and

one or more processors configured to interact with the data store, the one or more processors being further configured to perform operations comprising;

receiving, by the one or more processors, a query provided from a user device, the query including one or more n-grams that each include one or more terms; and

determining, by the one or more processors, that the query is implicitly about some entity for which an explicit reference to is absent from the one or more terms of the query, and in response;

obtaining, by the one or more processors, an approximate location of the user device when the user device provided the query,

obtaining, by the one or more processors and based on the approximate location of the user device, a set of entities, wherein each entity in the set of entities is a named place with a particular name and at a particular location, and each entity in the set of entities is obtained based on the particular location of the entity being within a threshold distance of the approximate location, and

determining, by the one or more processors, that the query is implicitly about an entity in the set of entities, and in response;

providing, by the one or more processors, a revised query based on the query and the particular name of the entity, the revised query explicitly referencing the entity by the particular name of the entity;

wherein;

determining that the query is implicitly about the entity in the set of entities that was obtained based on the approximate location of the user device comprises, for each entity in the set of entities;

accessing an index that associates entities with entity types and associates entity types with n-grams, wherein each entity type specifies a particular category to which a plurality of particular entities belong, and for each entity type, the index specifies n-grams that are determined be correlated to the entity type, and wherein each of the n-grams determined be correlated to the entity type are not n-grams that explicitly reference the particular entities that belong to the category specified by the entity type;

determining an entity type of the entity based on the index; and

determining whether the n-grams of the query correlate to the entity type of the entity based on the n-grams of the query matching n-grams that are determined be correlated to the entity type as specified in the index;

for each entity associated with the entity type to which the n-grams of the query correlate, including the entity in the sub-set of entities; and

selecting the entity from the subset of entities, wherein the subset of entities includes at least two or more entities, the selecting comprising;

determining that each of the entities in the subset of entities have a common attribute, wherein the common attribute for each entity relates to a popularity of the entity; and

selecting the entity with a highest popularity among the entities based on the common attribute.

5. The system of claim 4, wherein receiving a set of entities and determining that the query is implicitly about an entity in the set of entities are performed in response to determining that the approximate location is sufficiently fresh.

6. A non-transitory computer readable medium storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

receiving, by the one or more processors, a query provided from a user device, the query including one or more n-grams that each include one or terms; and

determining, by the one or more processors, that the query is implicitly about some entity for which an explicit reference to is absent from the one or more terms of the query, and in response;

obtaining, by the one or more processors, an approximate location of the user device when the user device provided the query,

obtaining, by the one or more processors and based on the approximate location of the user device, a set of entities, wherein each entity in the set of entities is a named place with a particular name and at a particular location, and each entity in the set of entities is obtained based on the particular location of the entity being within a threshold distance of the approximate location, and

determining, by the one or more processors, that the query is implicitly about an entity in the set of entities, and in response;

providing, by the one or more processors, a revised query based on the query and the particular name of the entity, the revised query explicitly referencing the entity by the particular name of the entity;

wherein;

determining that the query is implicitly about the entity in the set of entities that was obtained based on the approximate location of the user device comprises, for each entity in the set of entities;

accessing an index that associates entities with entity types and associates entity types with n-grams, wherein each entity type specifies a particular category to which a plurality of particular entities belong, and for each entity type, the index specifies n-grams that are determined be correlated to the entity type, and wherein each of the n-grams determined be correlated to the entity type are not n-grams that explicitly reference the particular entities that belong to the category specified by the entity type;

determining an entity type of the entity based on the index; and

determining whether the n-grams of the query correlate to the entity type of the entity based on the n-grams of the query matching n-grams that are determined be correlated to the entity type as specified in the index;

for each entity associated with the entity type to which the n-grams of the query correlate, including the entity in the sub-set of entities; and

selecting the entity from the subset of entities, wherein the subset of entities includes at least two or more entities, the selecting comprising;

determining that each of the entities in the subset of entities have a common attribute, wherein the common attribute for each entity relates to a popularity of the entity; and

selecting the entity with a highest popularity among the entities based on the common attribute.

7. The non-transitory computer readable medium of claim 6, wherein receiving a set of entities and determining that the query is implicitly about an entity in the set of entities are performed in response to determining that the approximate location is sufficiently fresh.