IDENTIFYING AND MEASURING RELATED QUERIES

• US 20080077588A1
• Filed: 11/30/2007
• Published: 03/27/2008
• Est. Priority Date: 02/28/2006
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Zhang, Wei, Jones, Rosie, Rey, Benjamin
• Application Number:
  US11/948,374
• Publication Number:
  US 20080077588A1
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/3332 Query translation
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A system and method are disclosed for identifying similar queries. A user query may be compared with known search keywords. The user query may be a Chinese related query, which is converted into a different form before comparing with other converted queries or keywords. A similarity score based on different features may be used for comparing the queries.

Claims

1. A method for matching queries with keywords comprising:

receiving a non-native language user query;

gathering a candidate set of the keywords to be compared with the user query;

converting the user query to a form for comparison with the keywords, wherein the keywords are converted to the form for comparison;

comparing the converted user query with each of the keywords, wherein a similarity score is established for each keyword to determine similarity with the user query; and

matching at least one keyword from the keywords with the user query based on the similarity score.

2. The method according to claim 1 wherein the non-native language user query comprises a Chinese related user query, wherein the Chinese related user query comprises at least one Chinese character.

3. The method according to claim 1 wherein each of the keywords are associated with at least one advertisement.

4. The method according to claim 3 further comprising:

providing the at least one advertisement that is associated with the matched at least one keyword.

5. The method according to claim 1 wherein the converting of the user query comprises at least one of adding, removing, or substituting at least one character from the user query.

6. The method according to claim 1 wherein the similarity score for each of the keywords is based on an edit distance with the converted user query.

7. In a computer readable storage medium having stored therein data representing instructions executable by a programmed processor for comparing a Chinese query with keywords, the storage medium comprising instructions operative for:

receiving the Chinese query;

selecting a set of the keywords for comparing with the Chinese query;

converting the Chinese query into at least one different form;

converting the set of keywords into the at least one different form;

determining at least one comparison between the Chinese query and the set of keywords, wherein the at least one comparison comprises a similarity score between the Chinese query and the set of keywords; and

identifying one of the set of keywords based on the similarity score.

8. The storage medium according to claim 7 wherein the at least one comparison comprises calculating an edit distance between the converted Chinese query and each of the converted set of keywords.

9. The storage medium according to claim 8 wherein the identified one of the set of keywords has a closest edit distance with the converted Chinese query.

10. The storage medium according to claim 7 wherein the at least one different form comprises a conversion of at least one character to at least one of a Chinese soundex form, a zhuyin form, a radicals form, a pinyin without tone form, a pinyin with tone form, or a Chinese utf8 form.

11. A method for determining similarity between queries comprising:

selecting at least two queries from a set of queries according to one language system;

converting each of the at least two queries into a different format, wherein the conversion comprises a transformation of certain characters in the at least two queries;

determining at least one comparison feature for each of the at least two queries; and

comparing the at least two queries based on the at least one comparison feature to determine a similarity between the at least two queries based on each of the at least one comparison feature.

12. The method according to claim 11 wherein the language system comprises Chinese, and the set of queries are Chinese related queries.

13. The method according to claim 12 wherein the transformation of certain characters in the at least two queries comprises changing at least one character into at least one of a Chinese soundex form, a zhuyin form, a radicals form, a pinyin without tone form, a pinyin with tone form, or a Chinese utf8 form.

14. The method according to claim 11 wherein the at least one comparison feature comprises at least one of comparing an edit distance, comparing a character level prefix overlap, or comparing a character level suffix overlap.

15. The method according to claim 14 wherein the comparing the edit distance further comprises comparing an edit distance by characters or an edit distance by words.

16. The method according to claim 11 wherein the at least two queries are converted into a plurality of different formats, wherein the comparing further comprises comparing the at least two queries in each of the plurality of different formats.

17. A method for comparing queries comprising:

receiving at least two queries, wherein each of the at least two queries comprise at least one Chinese representation;

converting the at least two queries into at least one common format;

calculating an edit distance between the converted at least two queries for each of the at least one common format; and

recording the edit distances between each of the converted at least two queries.

18. The method according to claim 17 wherein the at least one common format comprises an addition, subtraction, or substitution of at least one character.

19. The method according to claim 17 wherein the at least one common format comprises a conversion of at least one character into at least one of a Chinese soundex form, a zhuyin form, a radicals form, a pinyin without tone form, a pinyin with tone form, or a Chinese utf8 form

20. A system for measuring related queries comprising:

a search engine operative to receive a user search query;

an ad server coupled with the search engine and operative to provide an advertisement for display in response to the received user search query, wherein the ad server includes a plurality of search keywords, each of which are associated with at least one advertisement;

a search log database coupled with the search engine and operative to store search queries including the plurality of search keywords; and

a language analyzer coupled with the search engine that comprises;

a receiver operative to receive the user search query;

a converter coupled with the receiver and operative to convert the user search query into a different form;

a comparator coupled with the converter and operative to compare the converted search query with a candidate set of the plurality of search keywords; and

a calculator coupled with the comparator and operative to calculate a similarity score for each member of the candidate set based on the comparison with the converted search query;

wherein the associated at least one advertisement that is associated with the member of the candidate set with a closest similarity score is provided for display in response to the received search query.

21. The system according to claim 20 wherein the user search query is Chinese related and the converter is operative to change the Chinese related user search query into the different form by at least one of adding, deleting or substituting at least one of the characters of the Chinese related user search query.

22. The system according to claim 20 wherein the calculation of the similarity score comprises a computation of an edit distance between the converted user search query and the member of the candidate set.

23. The system according to claim 20 wherein the converter is operative to convert the candidate set of the plurality of search keywords into the different form for comparison with the converted user search query.