Using computational engines to improve search relevance

• US 8,606,739 B2
• Filed: 03/04/2011
• Issued: 12/10/2013
• Est. Priority Date: 06/30/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Apacible, Johnson T., Encarnacin, Mark J., Nareddy, Krishnamohan R.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US13/041,076
• Publication Number:
  US 20120005219A1
• Time in Patent Office: 1,012 Days
• Field of Search: None
• US Class Current: 706/50
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence

Abstract

An “Iterative Query Reformulator” provides various techniques for using a computational engine to reformulate initial queries through one or more iterations. This query reformulation process ensures that results returned from search engines or recommendation systems using a reformulated query have improved relevance relative to results that would have been returned using only the initial query. More specifically, the Iterative Query Reformulator provides an end to end solution that uses computations from one or more knowledge databases or knowledge sources to find “partial answers” to subqueries derived or extracted from an initial query. These partial answers are then used to reformulate the initial query, with the reformulated query being used by the search engines or recommendations systems to provide results that are highly relevant to the initial query. Determinations of whether to continue reformulation iterations are based on evaluating user metrics from historical search logs having queries that match reformulated queries.

Claims

1. A method for providing query results in response to a user query, comprising using a computing device to perform steps for:

receiving a current user query having multiple search terms;

evaluating the current user query to identify one or more subqueries, each subquery comprised of one or more of the search terms of the current user query;

evaluating each subquery to select one or more structured data sets from among a plurality of structured data sets from which to retrieve a partial answer corresponding each subquery;

for each partial answer retrieved from a selected structured data set, reformulating the current user query to construct a reformulated query by replacing the corresponding subquery of the current user query with the corresponding partial answer;

retrieving a set of ranked search results corresponding to reformulated query;

iteratively repeating the preceding steps, with the resulting reformulated query being used to replace the current user query in each iteration, until one or more of the ranked search results have a sufficiently high confidence level; and

when one or more of the ranked search results have a sufficiently high confidence level, presenting the set of ranked search results on a display device.

2. The method of claim 1 wherein evaluating the current user query to identify one or more subqueries further comprises steps for identifying one or more “

entities” and

associated “

properties”

that define entity characteristics.

3. The method of claim 1 further comprising steps for, prior to presenting the set of ranked search results on a display device, evaluating the ranked search results corresponding to reformulated query to determine a user satisfaction level from one or more historical user metrics relative to a predetermined threshold, and if the user satisfaction level is below the threshold, performing steps for:

evaluating the reformulated query to identify one or more subqueries, each subquery comprised of one or more of the search terms of the reformulated query;

evaluating each subquery to select one or more structured data sets from among a plurality of structured data sets from which to retrieve a partial answer corresponding each subquery;

for each partial answer retrieved from a selected structured data set, reformulating the previously reformulated query to construct a new reformulated query by replacing the corresponding subquery of the previously reformulated query with the corresponding partial answer; and

retrieving a set of ranked search results corresponding to the new reformulated query.

4. The method of claim 3 wherein the evaluating the ranked search results corresponding to current query to determine the user satisfaction level further comprises evaluating user click through rates (CTR) from historical search logs having entries corresponding to the ranked results to determine the user satisfaction level.

5. The method of claim 1 further comprising steps for providing a historical “

reformulation cache”

comprising a plurality of reformulated queries constructed from prior user queries of a plurality of users.

6. The method of claim 5 further comprising steps for, prior to evaluating the user query to identify one or more subqueries, checking the reformulation cache to determine whether the current user query has been previously reformulated, and if so, using the corresponding reformulated query from the reformulation cache to retrieve and present the set of ranked search results without identifying subqueries and retrieving partial answers for subqueries.

7. The method of claim 1 further comprising steps for receiving user feedback to select from two or more possible subqueries when evaluating the current user query to identify one or more subqueries.

8. The method of claim 1 wherein a computational engine is used to identify the subqueries, select the structured data sets, and retrieve the partial answers for each subquery.

9. The method of claim 1 wherein the set of ranked search results are presented to the user via a search engine user interface.

10. The method of claim 1 wherein the set of ranked search results are presented to the user via a recommendation system user interface.

11. A system for improving relevance of search results, comprising:

a user input device for receiving a current query from a user;

a user satisfaction measurement device for evaluating one or more user metrics within a set of historical search logs for determining a user satisfaction level for a set of query results corresponding to the current query;

a computational engine device for iteratively reformulating the current query to construct a new current query, with such iterations repeating until the user satisfaction level exceeds a predetermined threshold, and wherein iteratively reformulating the current query comprises;

evaluating the current query to identify one or more subqueries, each subquery comprised of one or more of the search terms of the current query,

evaluating each subquery to select one or more structured data sets from among a plurality of structured data sets from which to retrieve a partial answer corresponding each subquery,

for each partial answer retrieved from a selected structured data set, reformulating the current query to construct a new current query by replacing the corresponding subquery with the corresponding partial answer, and

retrieving a set of ranked search results corresponding to the new current query; and

presenting the set of ranked search results on a display device when the user satisfaction level exceeds the predetermined threshold.

12. The system of claim 11 wherein evaluating the current query to identify one or more subqueries further comprises identifying one or more “

entities” and

associated “

properties”

that define entity characteristics.

13. The system of claim 11 wherein determining the user satisfaction level further comprises evaluating user click through rates (CTR) from the historical search logs for entries corresponding to the ranked search results to determine the user satisfaction level.

14. The system of claim 11 further comprising a historical “

reformulation cache”

comprising a plurality of reformulated queries constructed from prior queries of a plurality of users, and, prior to iteratively reformulating the current query to construct the new current query;

checking the reformulation cache to determine whether the current query has been previously reformulated; and

if the current query has been previously reformulated, using the corresponding reformulated query from the reformulation cache to retrieve and present the ranked search results without performing the iterative reformulation.

15. The system of claim 11 further comprising a user feedback device for receiving user feedback to select from two or more possible subqueries when evaluating the current query to identify one or more subqueries.

16. A hardware computer-readable storage device having computer executable instructions stored therein for improving relevance of search results in response to a user query, said instructions comprising:

for receiving a current query from a user;

evaluating a set of historical search logs for determining a user satisfaction level for a set of query results returned in response to the current query;

iteratively reformulating the current query to construct a new current query, with such iterations repeating until the user satisfaction level exceeds a predetermined threshold, and wherein iteratively reformulating the current query comprises instructions for;

evaluating the current query to identify one or more subqueries, each subquery comprised of one or more of the search terms of the current query,

evaluating each subquery to select one or more structured data sets from among a plurality of structured data sets from which to retrieve a partial answer corresponding each subquery,

for each partial answer retrieved from a selected structured data set, reformulating the current query to construct a new current query by replacing the corresponding subquery with the corresponding partial answer, and

retrieving a set of ranked search results corresponding to the new current query; and

presenting the set of ranked search results on a display device when the user satisfaction level exceeds the predetermined threshold.

17. The computer-readable storage device of claim 16 wherein evaluating the current query to identify one or more subqueries further comprises identifying one or more “

entities” and

associated “

properties”

that define entity characteristics.

18. The computer-readable storage device of claim 16 wherein determining the user satisfaction level further comprises evaluating one or more user metrics from the historical search logs for entries corresponding to the ranked search results to determine the user satisfaction level.

19. The computer-readable storage device of claim 16 further comprising a historical “

reformulation cache”

comprising a plurality of reformulated queries constructed from prior queries of a plurality of users, and, prior to iteratively reformulating the current query to construct the new current query;

checking the reformulation cache to determine whether the current query has been previously reformulated; and

if the current query has been previously reformulated, using the corresponding reformulated query from the reformulation cache to retrieve and present the ranked search results without performing the iterative reformulation.

20. The computer-readable storage device of claim 16 further comprising receiving user feedback to select from two or more possible subqueries when evaluating the current query to identify one or more subqueries.