Adaptive Query Suggestion

• US 20140207746A1
• Filed: 01/22/2013
• Published: 07/24/2014
• Est. Priority Date: 01/22/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Song, Ruihua, Chen, Yu, Wen, Ji-Rong
• Granted Patent: US 10,108,699 B2
• Time in Patent Office: Days
• US Class Current: 707/706
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence

Abstract

When a user-submitted query is received, a set of candidate queries is identified. For each of the candidate queries, features are extracted that, for each candidate query, reflect a measure of effectiveness of the candidate query. The candidate queries are rank ordered based on the measure of effectiveness, and one or more of the top-ranked candidate queries are presented as suggested alternatives to the user-submitted query.

Claims

1. A method comprising:

receiving a user-submitted query;

identifying a plurality of candidate queries;

for each candidate query, extracting features that reflect an effectiveness of the candidate query;

rank ordering the candidate queries based at least in part on the features; and

suggesting one or more of the top-ranked candidate queries as alternate queries for the user-submitted query.

2. A method as recited in claim 1, wherein the features that reflect the effectiveness of the candidate query include match features that reflect how well the candidate query matches search results of the candidate query.

3. A method as recited in claim 2, wherein the match features include at least one of:

a title match that reflects how well the candidate query matches titles of the search results of the candidate query;

a snippet match that reflects how well the candidate query matches snippets of the search results of the candidate query;

or

a URL match that reflects how well the candidate query matches URLs of the search results of the candidate query.

4. A method as recited in claim 1, wherein the features that reflect the effectiveness of the candidate query include cross match features that reflect how well the user-submitted query matches search results of the candidate query.

5. A method as recited in claim 4, wherein the cross match features include at least one of:

a title cross match that reflects how well the user-submitted query matches titles of the search results of the candidate query;

a snippet cross match that reflects how well the user-submitted query matches snippets of the search results of the candidate query;

or

a URL cross match that reflects how well the user-submitted query matches URLs of the search results of the candidate query.

6. A method as recited in claim 1, wherein the features that reflect the effectiveness of the candidate query include similarity features that reflect similarities between search results of the user-submitted query and search results of the candidate query.

7. A method as recited in claim 6, wherein the similarity features include at least one of:

a page similarity that reflects a similarity between the content of the search results of the user-submitted query and the content of the search results of the candidate query;

a URL similarity that reflects a number of common URLs between the search results of the user-submitted query and the search results of the candidate query;

or

a domain similarity that reflects a number of common domains between the search results of the user-submitted query and the search results of the candidate query.

8. A method as recited in claim 1, wherein the features that reflect the effectiveness of the candidate query include an estimated normalized discounted cumulative gain (NDCG) value that reflects how relevant the search results of the candidate query are to the user-submitted query.

9. A method as recited in claim 8, wherein the estimated NDCG value is calculated based, at least in part, on an estimated relevance rating.

10. A method as recited in claim 9, wherein the estimated relevance rating represents, for each document in a set of search results, a number of times that the document is returned in the top n results of the candidate queries associated with the user-submitted query.

11. A method as recited in claim 1, wherein rank ordering the candidate queries based at least in part on the features comprises:

learning a ranking model based on training data; and

applying the ranking model to feature vectors for each of the candidate queries, wherein the feature vectors represent the features that are extracted.

12. A method as recited in claim 1, further comprising:

estimating a difficulty value associated with the user-submitted query;

in an event that the difficulty value is greater than a threshold value, preventing the identifying, extracting, rank ordering, and suggesting; and

in an event that the difficulty value is less than or equal to a threshold value, performing the identifying, extracting, rank ordering, and suggesting.

13. One or more computer-readable media encoded with computer-executable instructions that, when executed, configure a computer system to perform a method as recited in claim 1.

14. A web browser application at least partially stored in memory and executed on a processor to perform a method as recited in claim 1.

15. A method comprising:

receiving a user-submitted query;

determining whether the user-submitted query is a difficult query;

in an event that the user-submitted query is not a difficult query;

sending the user-submitted query to a search engine;

receiving search results associated with the user-submitted query from the search engine; and

presenting the search results associated with the user-submitted query; and

in an event that the user-submitted query is a difficult query;

identifying a plurality of candidate queries;

for each candidate query, calculating a usefulness probability value based at least in part on the candidate query and the user-submitted query, wherein the usefulness probability value reflects an estimated quality of the search results for the candidate query with respect to the user-submitted query;

rank ordering the candidate queries based on the usefulness probability values; and

suggesting one or more of the top-ranked candidate queries as alternate queries for the user-submitted query.

16. A method as recited in claim 15, further comprising:

in the event that the user-submitted query is a difficult query;

receiving a user selection of a particular query selected from the user-submitted query and the alternate queries that are suggested; and

presenting the search results associated with the particular query.

17. One or more computer-readable media encoded with computer-executable instructions that, when executed, configure a computer system to perform a method as recited in claim 15.

18. A method comprising:

receiving a user-submitted query;

identifying an ordered list of n suggested alternate queries, where n>

1;

for each suggested alternate query, calculating a normalized discounted cumulative gain (NDCG) to represent a retrieval performance of the suggested alternate query;

denoting a quality of the ordered list of n suggested alternate queries as Max@n, where Max@n is a maximum NDCG@k value among the n suggested alternate queries.

19. A method as recited in claim 18, further comprising:

denoting an overall quality of the ordered list of n suggested alternate queries as SDCG@n, where SDCG@n is calculated according to;

20. A method as recited in claim 18, wherein the NDCG that is calculated for each suggested alternate query is an estimated NDCG.