# US 2012/0254218 A1 · Enhanced Query Rewriting Through Statistical Machine Translation

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

- Number: US 2012/0254218 A1
- Document ID: US20120254218A1
- Status: Published application
- Kind: A1
- Application number: 13/078,648
- Filed: 2011-04-01
- Published: 2012-10-04
- Earliest claimed: 2011-04-01
- Assignees: Microsoft Corporation
- Inventors: Alnur Ali; Jianfeng Gao; Xiaodong He; Bodo von Billerbeck; Sanaz Ahari
- Web page: https://patentgrep.com/patent/US20120254218A1

## CPC

- G06F 16/3338: {Query expansion}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems, methods, and computer media for identifying query rewriting replacement terms are provided. A list of related string pairs each comprising a first string and second string is received. The first string of each related string pair is a user search query extracted from user click log data. For one or more of the related string pairs, the string pair is provided as inputs to a statistical machine translation model. The model identifies one or more pairs of corresponding terms, each pair of corresponding terms including a first term from the first string and a second term from the second string. The model also calculates a probability of relatedness for each of the one or more pairs of corresponding terms. Term pairs whose calculated probability of relatedness exceeds a threshold are characterized as query term replacements and incorporated, along with the probability of relatedness, into a query rewriting candidate database.

## Claims

### Claim 1

One or more computer storage media storing computer-executable instructions for performing a method for identifying query rewriting replacement terms, the method comprising:
receiving a list of related string pairs, each pair comprising a first string and a second string, wherein the first string of each related string pair is a user search query extracted from user click log data, and wherein the user click log data includes data for one or more search query sessions;
for one or more of the related string pairs, providing the string pair as inputs to a statistical machine translation model that:
identifies one or more pairs of corresponding terms, each pair of corresponding terms including a first term from the first string and a second term from the second string, and
calculates a probability of relatedness for each of the one or more pairs of corresponding terms; and
upon determining that the calculated probability of relatedness of a pair of corresponding terms exceeds a threshold:
characterizing the second term as a query term replacement for the first term, and
incorporating the first term, the second term, and the probability of relatedness for the pair into a query rewriting candidate database.

### Claim 2 (depends on 1)

The media of claim 1, wherein the statistical machine translation model is IBM model 1.

### Claim 3 (depends on 1)

The media of claim 1, wherein when a related string pair is identified as being highly related in the received list of pairs, additional instances of the string pair are input into the statistical machine translation model to create a weighting effect.

### Claim 4 (depends on 1)

The media of claim 1, wherein the statistical machine translation model is modified to identify groups of corresponding terms such that a probability of relatedness is calculated between a first group of two or more terms and a second group of two or more terms.

### Claim 5 (depends on 1)

The media of claim 1, wherein the second string of each related string pair is identified by analyzing the user click log data.

### Claim 6 (depends on 5)

The media of claim 5, wherein the second string of at least one related string pair is an additional search query extracted from the same search query session in the click log data as the corresponding first string.

### Claim 7 (depends on 5)

The media of claim 5, wherein the second string of at least one related string pair is the title or URL of a web page included in search results provided for either the user search query or an additional search query that was clicked on after the corresponding search results were provided.

### Claim 8 (depends on 5)

The media of claim 5, wherein the second string of at least one related string pair is a snippet corresponding to a web page included in search results provided for either the user search query or an additional search query that was clicked on after the corresponding search results were provided.

### Claim 9 (depends on 5)

The media of claim 5, wherein the second string of at least one related string pair is an additional user search query identified using random walk analysis such that the additional user search query is identified when a URL included in search results provided for the user search query is clicked on and a similar URL included in search results provided for the additional user search query is also clicked on.

### Claim 10

One or more computer storage media having a system embodied thereon including computer-executable instructions that, when executed, perform a method for identifying query rewriting replacement terms, the system comprising:
an intake component that receives a list of related string pairs, each pair comprising a first string and a second string, wherein the first string of each related string pair is a user search query extracted from user click log data, the user click log data including one or more search query sessions;
a statistical machine translation model that, for one or more of the related string pairs:
receives the string pair as inputs,
identifies one or more pairs of corresponding terms, each pair of corresponding terms including a first term from the first string and a second term from the second string, and
calculates a probability of relatedness for each of the one or more pairs of corresponding terms;
a characterization component that, upon determining that the probability of relatedness of a pair of corresponding terms calculated by the statistical machine translation model exceeds a threshold, characterizes the second term as a query term replacement for the first term; and
a candidate term population component that, for each pair of corresponding terms for which the calculated probability of relatedness exceeds a threshold, incorporates the first term, the second term, and the probability of relatedness for the pair into a query rewriting candidate database.

### Claim 11 (depends on 10)

The media of claim 10, wherein the statistical machine translation model is IBM model 1.

### Claim 12 (depends on 10)

The media of claim 10, wherein when a related string pair is identified as being highly related in the received list of pairs, additional instances of the string pair are input into the statistical machine translation model to create a weighting effect.

### Claim 13 (depends on 10)

The media of claim 10, wherein the statistical machine translation model is modified to identify groups of corresponding terms such that a probability of relatedness is calculated between a first group of two or more terms and a second group of two or more terms.

### Claim 14 (depends on 10)

The media of claim 10, wherein the second string of each related string pair is identified by analyzing the user click log data.

### Claim 15 (depends on 14)

The media of claim 14, wherein the second string of at least one related string pair is an additional search query extracted from the same search query session in the click log data as the corresponding first string.

### Claim 16 (depends on 14)

The media of claim 14, wherein the second string of at least one related string pair is the title or URL of a web page included in search results provided for either the user search query or an additional search query that was clicked on after the corresponding search results were provided.

### Claim 17 (depends on 14)

The media of claim 14, wherein the second string of at least one related string pair is a snippet corresponding to a web page included in search results provided for either the user search query or an additional search query that was clicked on after the corresponding search results were provided.

### Claim 18 (depends on 14)

The media of claim 14, wherein the second string of at least one related string pair is an additional user search query identified using random walk analysis such that the additional user search query is identified when a URL included in search results provided for the user search query is clicked on and a similar URL included in search results provided for the additional user search query is also clicked on.

### Claim 19

One or more computer storage media storing computer-executable instructions for performing a method for identifying query rewriting replacement terms, the method comprising:
receiving a list of related string pairs, each pair comprising a first string and a second string, wherein the first string of each related string pair is a user search query extracted from user click log data, wherein the user click log data including data for one or more search query sessions, and wherein the second string of each related string pair is identified by analyzing the user click log data;
for one or more of the related string pairs, providing the string pair as inputs to a statistical machine translation model that:
identifies one or more pairs of corresponding terms, each pair of corresponding terms including a first term from the first string and a second term from the second string, and
calculates a probability of relatedness for each of the one or more pairs of corresponding terms,
wherein when a related string pair is identified as being highly related in the received list of pairs, additional instances of the string pair are input into the statistical machine translation model to create a weighting effect; and
upon determining that the calculated probability of relatedness of a pair of corresponding terms exceeds a threshold:
characterizing the second term as a query term replacement for the first term, and
incorporating the first term, the second term, and the probability of relatedness for the pair into a query rewriting candidate database.

### Claim 20 (depends on 19)

The media of claim 19, wherein the statistical machine translation model is modified to identify groups of corresponding terms such that a probability of relatedness is calculated between a first group of two or more terms and a second group of two or more terms.
