Identifying query formulation suggestions for low-match queries

• US 8,965,872 B2
• Filed: 06/29/2011
• Issued: 02/24/2015
• Est. Priority Date: 04/15/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hsu, Bo-June, Wang, Kuansan, Kuo, Yu-Ting, Shum, Heung-Yeung, Liu, Chao-Chia
• Primary Examiner(s): Chen, Susan
• Application Number:
  US13/172,561
• Publication Number:
  US 20120265787A1
• Time in Patent Office: 1,336 Days
• Field of Search: 704/4, 705/3, 386/252, 707/711
• US Class Current: 707/706
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri

Abstract

Systems, methods and computer-storage media are provided for identifying low-match search queries and determining comparable item matches to suggest to the user in response to a low-match query. “Low-match queries” are queries for which an insufficient number of exact item matches are available. In embodiments, exact and/or comparable item matches may be determined via semantic analysis. Also provided are systems, methods and computer-storage media for informing the user, by way of a presented indicator, or the like, that a presented item was selected for presentation based upon a similarity metric rather than being determined an exact match for the input query.

Claims

1. A method performed by a computing device having a processor and a memory for identifying comparable item matches for search queries, the method comprising:

receiving at least a portion of a search query inputted on a Web page associated with a search engine;

accessing an entity data store comprising one or more entities, and one or more categories associated with the one or more entities, wherein the one or more entities are items having associated information and are associated with at least one of the one or more categories;

using the entity data store, identifying a number of exact item matches for the at least a portion of the search query;

determining that the number of exact item matches is below a predefined threshold; and

upon determining that the number of exact item matches is below the predefined threshold, using the entity data store to identify comparable item matches for the at least a portion of the search query, wherein using the entity data store to identify the comparable item matches for the at least the portion of the search query comprises;

(1) assigning a similarity score to each of a plurality of non-matching entities in the entity data store that indicates a relative similarity to at least one of the exact item matches,

(2) comparing the similarity score to a predefined similarity score,

(3) generating query formulation suggestions using a portion of the plurality of non-matching entities that have similarity scores greater than the predefined similarity score, the portion of the plurality of non-matching entities comprising comparable item matches, and

(4) presenting at least a portion of the query formulation suggestions on the Web page associated with the search engine.

2. The method of claim 1, wherein the predefined similarity score is user-specified.

3. The method of claim 1, further comprising utilizing at least a portion of the exact item matches to further generate additional query formulation suggestions, and transmitting at least a portion of the additional query formulation suggestions for presentation.

4. The method of claim 3, wherein presenting the at least the portion of the query formulation suggestions on the Web page associated with the search engine further comprises transmitting an indicator of which query formulation suggestions were generated utilizing comparable item matches.

5. The method of claim 1, further comprising utilizing at least a portion of the comparable item matches to generate related query suggestions and transmitting at least a portion of the generated related query suggestions for presentation.

6. The method of claim 1, further comprising transmitting the exact item matches and at least a portion of the comparable item matches for presentation as query results.

7. The method of claim 6, wherein transmitting the exact item matches and the at least a portion of the comparable item matches for presentation as query results further comprises transmitting an indicator of which query results are comparable item matches.

8. The method of claim 1, wherein the similarity score is based in part on a semantic similarity between the each of the plurality of non-matching entities and the at least one of the exact item matches.

9. The method of claim 1, wherein the similarity score is based in part on numeric similarity between the each of the plurality of non-matching entities and the at least one of the exact item matches.

10. The method of claim 1, wherein the similarity score is based in part on a spelling similarity between the each of the plurality of non-matching entities and the at least one of the exact item matches.

11. The method of claim 1, wherein the similarity score is based in part on a geographic similarity between the each of the plurality of non-matching entities and the at least one of the exact item matches.

12. The method of claim 1, wherein the similarity score is based in part on a temporal similarity between the each of the plurality of non-matching entities and the at least one of the exact item matches.

13. The method of claim 1, wherein the similarity score is based in part on a social similarity between the each of the plurality of non-matching entities and the at least one of the exact item matches.

14. One or more computer-storage media storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method for identifying query formulation suggestions, the method comprising:

receiving at least a portion of a search query inputted on a Web page associated with a search engine, the at least the portion of the search query having at least one specified hierarchical characteristic comprising a category or an attribute;

accessing an entity data store comprising one or more entities, and one or more categories associated with the one or more entities, and one or more attributes associated with the one or more entities, wherein the one or more entities are items having associated information and are associated with at least one of the one or more categories, or the one or more attributes;

using the entity data store, identifying a number of exact item matches for the at least a portion of the search query;

using the entity data store, identifying comparable item matches for the at least a portion of the search query, wherein using the entity data store to identify comparable item matches for the at least the portion of the search query comprises;

(1) identifying a plurality of non-matching entities in the entity data store having one or more hierarchical characteristics,

(2) assigning a similarity score to each hierarchical characteristic for each of the plurality of non-matching entities that indicates a relative similarity to at least one of the exact item matches;

(3) determining an overall similarity score for each of the plurality of non-matching entities,

(4) comparing the overall similarity score to a predefined similarity score, and

(5) identifying as comparable item matches those non-matching entities that have an overall similarity score greater than the predefined similarity score;

utilizing at least a portion of the exact item matches and at least a portion of the comparable item matches to generate query formulation suggestions;

transmitting at least a portion of the generated query formulation suggestions for presentation; and

presenting the at least the portion of the generated query formulation suggestions on the Web page associated with the search engine.

15. The one or more computer-storage media of claim 14, wherein the method further comprises receiving a user-indication that utilization of comparable item matches for generating query formulation suggestions is desired.

16. The one or more computer-storage media of claim 14, wherein the predefined similarity score is user-specified.

17. The one or more computer-storage media of claim 14, wherein presenting the at least the portion of the generated query formulation suggestions on the Web page associated with the search engine further comprises transmitting an indicator of which query formulation suggestions were generated utilizing comparable item matches.

18. The one or more computer-storage media of claim 14, wherein the similarity score is based on one or more of semantic similarity, numeric similarity, spelling similarity, geographic similarity, temporal similarity, and social similarity with respect to the at least one of the exact item matches.

19. One or more computer-storage media storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method for identifying query formulation suggestions, the method comprising:

receiving at least a portion of a search query inputted on a Web page associated with a search engine, the at least the portion of the search query having at least one entity and at least one hierarchical characteristic associated with the at least one entity, wherein an entity is an item having associated information;

accessing an entity data store comprising one or more entities, and one or more categories associated with the one or more entities, and one or more attributes associated with the one or more entities, and one or more attribute values associated with the one or more entities, wherein the one or more entities are associated with at least one of the one or more categories, or the one or more attributes, or the one or more attribute values;

using the entity data store, identifying a number of entities that exactly match (known as “

exact entity matches”

) the at least one entity associated with the at least a portion of the search query;

determining that an insufficient number of exact entity matches are identified;

using the entity data store, identifying a plurality of non-matching entities having one or more hierarchical characteristics that have one or more of semantic similarity, numeric similarity, spelling similarity, geographic similarity, temporal similarity, and social similarity with respect to the at least the portion of the search query, the plurality of non-matching entities comprising comparable entity matches;

utilizing at least a portion of the exact entity matches and at least a portion of the comparable entity matches to generate query formulation suggestions;

transmitting at least a portion of the generated query formulation suggestions for presentation; and

presenting the at least the portion of the generated query formulation suggestions on the Web page associated with the search engine.