# US 8,543,580 B2 · Mining translations of web queries from web click-through data

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

- Number: US 8,543,580 B2
- Document ID: US8543580B2
- Status: Granted
- Kind: B2
- Application number: 12/342,098
- Filed: 2008-12-23
- Published: 2010-06-24
- Granted: 2013-09-24
- Earliest claimed: 2008-12-23
- Assignees: Microsoft Corporation
- Applicants: Weizhu Chen; Zheng Chen
- Inventors: Weizhu Chen; Zheng Chen
- Web page: https://patentgrep.com/patent/US8543580B2

## CPC

- G06F 16/9566: {URL specific, e.g. using aliases, detecting broken or misspelled links}
- G06F 16/951: Indexing; Web crawling techniques
- G06F 16/953: Querying, e.g. by the use of web search engines
- G06F 2216/03: Data mining
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and technologies providing translations of web queries based on an analysis of user behavior in click-through data. These methods and technologies generates large-scale and timely query translation pairs guided by a small set of seed word pairs from a dictionary, without relying on additional knowledge or complex models.

## Claims

### Claim 1

A method performed on a computing device and for generating a query translation pair, the method comprising:
establishing a plurality of seed query pairs that each comprise a source language query and a target language query that have the same meaning but are in different languages, where the source language query is different for each of the plurality of seed query pairs;
finding a plurality of URL pairs from click-through data, the plurality of URL pairs based on the seed query pair;
extracting URL pair patterns from ones of the plurality of URL pairs having a similarity score above a particular threshold;
extracting from the click-through data bilingual URL pairs identified by the URL pair patterns;
identifying in the click-through data candidate query pairs corresponding to the bilingual URL pairs; and
filtering the candidate query pairs based on a confidence score resulting in a query translation pair where queries of the query translation pair are translations of each other.

### Claim 2 (depends on 1)

The method of claim 1 wherein the similarity score is calculated as
sim
⁡
(
u
i
s
,
u
i
t
)
=
1
-
EditDistance
⁡
(
u
i
s
,
u
i
t
)
min
⁡
(

u
i
s

,

u
i
t

)
where uis represents a first URL corresponding to the source language query, where uit represents a second URL corresponding to the target language query, where the EditDistance( ) function contributes to the similarity score based on a minimum number of edit operations required to transform a first URL into a second URL, and where the min( ) function selects a shorter of the first and second URLs.

### Claim 3 (depends on 1)

The method of claim 1 wherein the seed query pair is taken least in part from a bilingual dictionary.

### Claim 4 (depends on 1)

The method of claim 1 wherein each of the plurality of URL pairs is found by identifying the most-clicked URL associated with each query of one of the plurality of seed query pairs.

### Claim 5 (depends on 1)

The method of claim 1 wherein the extracted bilingual URL pairs follow at least one pattern identified by the URL pair patterns.

### Claim 6 (depends on 1)

The method of claim 1 wherein a candidate query pair of the candidate query pairs is formed using queries of a click-through data pair in which a URL of each of the click-through data pair matches a unique one of another URL of a particular bilingual URL pair of the bilingual URL pairs.

### Claim 7 (depends on 1)

The method of claim 1 wherein the filtering removes noisy candidate query pairs.

### Claim 8

At least one computer storage device storing computer-executable instructions that, when executed by a computing device, cause the computing device to perform actions for generating a query translation pair, the actions comprising:
establishing a plurality of seed query pairs that each comprise a source language query and a target language query that have the same meaning but are in different languages, where the source language query is different for each of the plurality of seed query pairs;
finding a plurality of URL pairs from click-through data, the plurality of URL pairs based on the seed query pair;
extracting URL pair patterns from ones of the plurality of URL pairs having a similarity score above a particular threshold;
extracting from the click-through data bilingual URL pairs identified by the URL pair patterns;
identifying in the click-through data candidate query pairs corresponding to the bilingual URL pairs; and
filtering the candidate query pairs based on a confidence score resulting in a query translation pair where queries of the query translation pair are translations of each other.

### Claim 9 (depends on 8)

The at least one computer storage device of claim 8 where the similarity score is calculated as
sim
⁡
(
u
i
s
,
u
i
t
)
=
1
-
EditDistance
⁡
(
u
i
s
,
u
i
t
)
min
⁡
(

u
i
s

,

u
i
t

)
where uis represents a first URL corresponding to the source language query where uit represents a second URL corresponding to the target language query, where the EditDistance( ) function results in the similarity score based on a minimum number of edit operations required to transform a first URL into a second URL, and where the min( ) function selects a shorter of the first and second URLs.

### Claim 10 (depends on 8)

The at least one computer storage device of claim 8 where the seed query pair is taken least in part from a bilingual dictionary.

### Claim 11 (depends on 8)

The at least one computer storage device of claim 8 where each of the plurality of URL pairs is found by identifying the most-clicked URL associated with each query of one of the plurality of seed query pairs.

### Claim 12 (depends on 8)

The at least one computer storage device of claim 8 where the extracted bilingual URL pairs follow at least one pattern identified by the URL pair patterns.

### Claim 13 (depends on 8)

The at least one computer storage device of claim 8 where a candidate query pair of the candidate query pairs is formed using queries of a click-through data pair in which a URL of each of the click-through data pair matches a unique one of another URL of a particular bilingual URL pair of the bilingual URL pairs.

### Claim 14

A computing device and at least one software module together configured for generating a query translation pair based on:
establishing a plurality of seed query pairs that each comprise a source language query and a target language query that have the same meaning but are in different languages, where the source language query is different for each of the plurality of seed query pairs;
finding a plurality of URL pairs from click-through data, the plurality of URL pairs based on the seed query pair;
extracting URL pair patterns from ones of the plurality of URL pairs having a similarity score above a particular threshold;
extracting from the click-through data bilingual URL pairs identified by the URL pair patterns;
identifying in the click-through data candidate query pairs corresponding to the bilingual URL pairs; and
filtering the candidate query pairs based on a confidence score resulting in a query translation pair where queries of the query translation pair are translations of each other.

### Claim 15 (depends on 14)

The computing device and at least one software module of claim 14 where the similarity score is calculated as
sim
⁡
(
u
i
s
,
u
i
t
)
=
1
-
EditDistance
⁡
(
u
i
s
,
u
i
t
)
min
⁡
(

u
i
s

,

u
i
t

)
where uis represents a first URL corresponding to the source language query, where uit represents a second URL corresponding to the target language query, where the EditDistance( ) function contributes to the similarity score based on a minimum number of edit operations required to transform a first URL into a second URL, and where the min( ) function selects a shorter of the first and second URLs.

### Claim 16 (depends on 14)

The computing device and at least one software module of claim 14 where the seed query pair is taken least in part from a bilingual dictionary.

### Claim 17 (depends on 14)

The computing device and at least one software module of claim 14 where each of the plurality of URL pairs is found by identifying the most-clicked URL associated with each query of one of the plurality of seed query pairs.

### Claim 18 (depends on 14)

The computing device and at least one software module of claim 14 where the extracted bilingual URL pairs follow at least one pattern identified by the URL pair patterns.

### Claim 19 (depends on 14)

The computing device and at least one software module of claim 14 where a candidate query pair of the candidate query pairs is formed using queries of a click-through data pair in which a URL of each of the click-through data pair matches a unique one of another URL of a particular bilingual URL pair of the bilingual URL pairs.

### Claim 20 (depends on 14)

The computing device and at least one software module of claim 14 where the filtering removes noisy candidate query pairs.