# US 2014/0207746 A1 · Adaptive Query Suggestion

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0207746 A1
- Document ID: US20140207746A1
- Status: Published application
- Kind: A1
- Application number: 13/747,274
- Filed: 2013-01-22
- Published: 2014-07-24
- Earliest claimed: 2013-01-22
- Assignees: Microsoft Corporation
- Applicants: Microsoft Corporation
- Inventors: Ruihua Song; Yu Chen; Ji-Rong Wen
- Web page: https://patentgrep.com/patent/US20140207746A1

## CPC

- G06F 16/3322: {using system suggestions (G06F16/3325 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 8)

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

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 1)

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.

### Claim 12 (depends on 1)

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.

### Claim 13 (depends on 1)

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.

### Claim 14 (depends on 1)

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

### Claim 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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 15)

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.

### Claim 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.

### Claim 19 (depends on 18)

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:
SDCG
@
n
=
∑
i
=
1
n

NDCG
@
k

(
i
)
log

(
1
+
i
)
where NDCG@k(i) is the quality of the suggestion at position i.

### Claim 20 (depends on 18)

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