Translation-based query pattern mining

• US 8,655,901 B1
• Filed: 06/23/2010
• Issued: 02/18/2014
• Est. Priority Date: 06/23/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Li, Xin, Chen, Shi
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US12/821,978
• Time in Patent Office: 1,336 Days
• Field of Search: 707/713, 707/758, 707/760, 704/7, 704/8
• US Class Current: 707/760
• CPC Class Codes: G06F 16/3337 Translation of the query language, e.g. Chinese to English
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/58 Use of machine translation, e.g. for multi-lingual retrieval, for server-side translation for client devices or for real-time translation

Abstract

This specification describes technologies relating to search systems. In general, one aspect of the subject matter described in this specification can be embodied in methods that include the actions of receiving a query pattern, the query pattern identifying a particular rule to interpret a particular type of query, the query pattern being in a first language; identifying a collection of queries in the first language matching the query pattern; annotating each query of the collection of queries with one or more labels; translating the collection of annotated queries in the first language into a translated collection of queries in a second language; aligning the translated collection of queries including identifying a most common term in the translated collection of queries and determining the corresponding positions of the annotations relative to the translated query terms; and extracting a translated query pattern from the aligned translated collection of queries.

Claims

1. A method comprising:

receiving a first query pattern, the query pattern identifying a particular rule to interpret a particular type of query, the query pattern being in a first language;

identifying, with a system comprising one or more computing devices, a collection of queries in the first language matching the query pattern by determining which queries in a query log match the query pattern;

segmenting a given query among the collection into one or more tokens in the first language, wherein each token includes one or more terms from the given query;

annotating each query of the collection of queries with one or more labels identifying the parts of each query, wherein annotating each query of the collection of queries with one or more labels comprises;

associating each of the one or more tokens with corresponding components of the first query pattern; and

annotating the one or more tokens with labels for the corresponding components of the first query pattern;

translating the collection of annotated queries in the first language into a translated collection of queries in a second language; and

extracting a translated query pattern from the translated collection of queries, wherein for the given one of the plurality of queries, extracting a translated query pattern from the translated collection of queries comprises;

determining, from an order in which the one or more tokens into which the given query was segmented in the first language are translated into the second language, an order in which labels for the components of the first query pattern correspond to translated terms of the given query; and

extracting the translated query pattern from the order in which labels for the components of the first query pattern correspond to the translated terms of the given query pattern.

2. The method of claim 1, further comprising:

using the translated query pattern to interpret received queries in the second language matching the translated query pattern.

3. The method of claim 2, where using the translated query pattern includes applying the translated query pattern to a received query in order to identify one or more query splits into query components and using the resulting query components to search a respective index for each query component.

4. The method of claim 1, further comprising:

using the translated query pattern to search for results responsive to a received query in the second language and presenting search results.

5. The method of claim 1, where identifying a collection of queries includes identifying queries from a query log that match the first query pattern.

6. The method of claim 1, where annotating each query includes labeling portions of the query according to the first query pattern.

7. The method of claim 1, where extracting a translated query pattern further comprises cross-validating the translated query pattern with a query log with respect to a specified occurrence threshold.

8. A system comprising:

one or more processors configured to interact with a computer-readable medium in order to perform operations comprising;

receiving a first query pattern, the query pattern identifying a particular rule to interpret a particular type of query, the query pattern being in a first language;

identifying a collection of queries in the first language matching the query pattern by determining which queries in a query log match the query pattern;

segmenting a given query among the collection into one or more tokens in the first language, wherein each token includes one or more terms from the given query;

annotating each query of the collection of queries with one or more labels identifying the parts of each query, wherein annotating each query of the collection of queries with one or more labels comprises;

associating each of the one or more tokens with corresponding components of the first query pattern; and

annotating the one or more tokens with labels for the corresponding components of the first query pattern;

translating the collection of annotated queries in the first language into a translated collection of queries in a second language; and

extracting a translated query pattern from the translated collection of queries, wherein for the given one of the plurality of queries, extracting a translated query pattern from the translated collection of queries comprises;

determining, from an order in which the one or more tokens into which the given query was segmented in the first language are translated into the second language, an order in which labels for the components of the first query pattern correspond to translated terms of the given query; and

extracting the translated query pattern from the order in which labels for the components of the first query pattern correspond to the translated terms of the given query pattern.

9. The system of claim 8, further configured to perform operations comprising:

using the translated query pattern to interpret received queries in the second language matching the translated query pattern.

10. The system of claim 9, where using the translated query pattern includes applying the translated query pattern to a received query in order to identify one or more query splits into query components and using the resulting query components to search a respective index for each query component.

11. The system of claim 8, further configured to perform operations comprising:

using the translated query pattern to search for results responsive to a received query in the second language and presenting search results.

12. The system of claim 8, where identifying a collection of queries includes identifying queries from a query log that match the first query pattern.

13. The system of claim 8, where annotating each query includes labeling portions of the query according to the first query pattern.

14. The system of claim 8, where extracting a translated query pattern further comprises cross-validating the translated query pattern with a query log with respect to a specified occurrence threshold.

15. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving a first query pattern, the query pattern identifying a particular rule to interpret a particular type of query, the query pattern being in a first language;

identifying a collection of queries in the first language matching the query pattern by determining which queries in a query log match the query pattern;

segmenting a given query among the collection into one or more tokens in the first language, wherein each token includes one or more terms from the given query;

annotating each query of the collection of queries with one or more labels identifying the parts of each query, wherein annotating each query of the collection of queries with one or more labels comprises;

associating each of the one or more tokens with corresponding components of the first query pattern; and

annotating the one or more tokens with labels for the corresponding components of the first query pattern;

translating, with a system comprising one or more computing devices, the collection of annotated queries in the first language into a translated collection of queries in a second language; and

extracting a translated query pattern from the translated collection of queries, wherein for the given one of the plurality of queries, extracting a translated query pattern from the translated collection of queries comprises;

determining, from an order in which the one or more tokens into which the given query was segmented in the first language are translated into the second language, an order in which labels for the components of the first query pattern correspond to translated terms of the given query; and

extracting the translated query pattern from the order in which labels for the components of the first query pattern correspond to the translated terms of the given query pattern.