Query rewriting with entity detection

• US 7,996,419 B2
• Filed: 03/31/2004
• Issued: 08/09/2011
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pfleger, Karl
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Darno; Patrick A
• Application Number:
  US10/813,359
• Publication Number:
  US 20050222976A1
• Time in Patent Office: 2,687 Days
• Field of Search: 707/5, 707/706, 707/768, 707/999.002, 707/999.003, 707/999.005
• US Class Current: 707/768
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system determines whether a received search query includes an entity name, determines whether to rewrite the received search query based on information relating to prior searches involving the entity name, and rewrites the received search query when it is determined that the received search query should be rewritten. The system further determines whether to provide a suggestion of rewriting the received search query, as a rewriting suggestion, based on information relating to prior searches involving the entity name when it is determined that the received search query should not be rewritten. The system also generates the rewriting suggestion when it is determined that the rewriting suggestion should be provided. The system performs a search based on one of the received search query and the rewritten search query to obtain search results, presents the search results, and presents the rewriting suggestion when it is determined that the rewriting suggestion should be provided.

Claims

1. A method, comprising:

receiving, by one or more processors of one or more servers, a query log comprising entries associating prior search queries with selected entity identifiers,

selecting, by one or more processors of one or more servers, a candidate string, from a list of candidate strings, where the candidate string appears in search queries associated with a common entity identifier, of the selected entity identifiers, in the query log and where the candidate string is selected based on a distribution of different candidate strings appearing in prior search queries associated with the common entity identifier,

where the candidate string is selected based on how statistically peaked a count of clicks for the candidate string is compared to counts of clicks for one or more other candidate strings, and

where the candidate string is selected based on entropy of the distribution of counts of clicks for the different candidate strings, and

adding, by one or more processors of one or more servers, the candidate string to a query rewrite table, where the candidate string is associated with the common entity identifier and where, when a previously presented search query is received, the query rewrite table is used to identify the candidate string and include the common entity identifier in a rewritten search query.

2. The method of claim 1, where the count of clicks for the candidate string comprises a count of clicks on an entity identifier given a candidate string appearing in a prior search query of the query log.

3. The method of claim 1, where the candidate string is selected based on whether the count of clicks for the candidate string exceeds a combined count of clicks for the one or more other candidate strings.

4. The method of claim 1, where the entries of the query log include user behavior information and where the candidate string is selected based on the user behavior information.

5. The method of claim 4, where the user behavior information includes whether a conversion occurred associated with the common entity identifier.

6. The method of claim 4, where the user behavior information includes how much time a user spends accessing the common entity identifier.

7. The method of claim 1, where the common entity identifier is a hostname.

8. The method of claim 1, where the common entity identifier is a product identifier.

9. The method of claim 1, where the rewritten search query is used to provide search results to a user.

10. The method of claim 1, where the rewritten search query is used to provide a suggested search query to a user.

11. A method, comprising:

receiving, by one or more processors of one or more servers, a search query, and

when the search query includes a string in a query rewrite table, rewriting the search query to a rewritten search query that includes an entity identifier associated with the string in the query rewrite table, where the query rewrite table is constructed by;

receiving, by one or more processors of one or more servers, a query log comprising entries associating prior search queries with selected entity identifiers;

selecting, by one or more processors of one or more servers, a candidate string from a list of candidate strings, where the candidate string appears in search queries associated with a common entity identifier, of the selected entity identifiers, in the query log and where the candidate string is selected based on a distribution of different candidate strings appearing in prior search queries associated with the common entity identifier,

where the candidate string is selected based on how statistically peaked a count of clicks for the candidate string is compared to counts of clicks for one or more other candidate strings, and

where the candidate string is selected based on entropy of the distribution of counts of clicks for the different candidate strings; and

adding, by one or more processors of one or more servers, the candidate string to the query rewrite table, where the candidate string is associated with the common entity identifier.

12. The method of claim 11, where the count of clicks for the candidate string comprises a count of clicks on an entity identifier given a candidate string appearing in a prior search query of the query log.

13. The method of claim 11, where the candidate string is selected based on whether the count of clicks for the candidate string exceeds a combined count of clicks for the one or more other candidate strings.

14. The method of claim 11, where the entries of the query log include user behavior information and where the candidate string is selected based on the user behavior information.

15. The method of claim 14, where the user behavior information includes whether a conversion occurred associated with the common entity identifier.

16. The method of claim 14, where the user behavior information includes how much time a user spends accessing the common entity identifier.

17. The method of claim 11, where the common entity identifier is a hostname.

18. The method of claim 11, where the common entity identifier is a product identifier.

19. The method of claim 11, where the rewritten search query is used to provide search results to a user.

20. The method of claim 11, where the rewritten search query is used to provide a suggested search query to a user.

21. A system, comprising:

one or more devices comprising;

means for receiving a query log comprising entries associating prior search queries with selected entity identifiers,

means for selecting a candidate string, from a list of candidate strings, where the candidate string appears in search queries associated with a common entity identifier, of the selected entity identifiers, in the query log and where the candidate string is selected based on a distribution of different candidate strings appearing in prior search queries associated with the common entity identifier,

where the candidate string is selected based on how statistically peaked a count of clicks for the candidate string is compared to counts of clicks for one or more other candidate strings, and

where the candidate string is selected based on entropy of the distribution of counts of clicks for the different candidate strings, and

means for adding the candidate string to a query rewrite table, where the candidate string is associated with the common entity identifier and where, when a previously presented search query is received, the query rewrite table is used to identify the candidate string and include the common entity identifier in a rewritten search query.

22. A system comprising:

one or more devices configured to;

receive a query log comprising entries associating prior search queries with selected entity identifiers,

select a candidate string, from a list of candidate strings, where the candidate string appears in search queries associated with a common entity identifier, of the selected entity identifiers, in the query log and where the candidate string is selected based on a distribution of different candidate strings appearing in prior search queries associated with the common entity identifier,

where the candidate string is selected based on how statistically peaked a count of clicks for the candidate string is compared to counts of clicks for one or more other candidate strings, and

where the candidate string is selected based on entropy of the distribution of counts of clicks for the different candidate strings, and

add the candidate string to a query rewrite table, where the candidate string is associated with the common entity identifier and where, when a previously presented search query is received, the query rewrite table is used to identify the candidate string and include the common entity identifier in a rewritten search query.

23. The system of claim 22, where the count of clicks for the candidate string comprises a count of clicks on an entity identifier given a candidate string appearing in a prior search query of the query log.

24. The system of claim 22, where the candidate string is selected based on whether the count of clicks for the candidate string exceeds a combined count of clicks for the one or more other candidate strings.

25. The system of claim 22, where the entries of the query log include user behavior information and where the candidate string is selected based on the user behavior information.

26. The system of claim 25, where the user behavior information includes whether a conversion occurred associated with the common entity identifier.

27. The system of claim 25, where the user behavior information includes how much time a user spends accessing the common entity identifier.

28. The system of claim 22, where the common entity identifier is a hostname.

29. The system of claim 22, where the common entity identifier is a product identifier.

30. The system of claim 22, where the rewritten search query is used to provide search results to a user.

31. The system of claim 22, where the rewritten search query is used to provide a suggested search query to a user.

32. A system comprising:

one or more devices configured to;

receive a search query, and

when the search query includes a string in a query rewrite table, rewrite the search query to a rewritten search query that includes an entity identifier associated with the string in the query rewrite table, where at least one of the one or more devices is configured to construct the query rewrite table,

where, when constructing the query rewrite table, the at least one of the one or more devices is configured to;

receive a query log comprising entries associating prior search queries with selected entity identifiers;

select a candidate string from a list of candidate strings, where the candidate string appears in search queries associated with a common entity identifier, of the selected entity identifiers, in the query log and where the candidate string is selected based on a distribution of different candidate strings appearing in prior search queries associated with the common entity identifier,

where the candidate string is selected based on how statistically peaked a count of clicks for the candidate string is compared to counts of clicks for one or more other candidate strings, and

where the candidate string is selected based on entropy of the distribution of counts of clicks for the different candidate strings; and

add the candidate string to the query rewrite table, where the candidate string is associated with the common entity identifier.

33. The system of claim 32, where the count of clicks for the candidate string comprises a count of clicks on an entity identifier given a candidate string appearing in a prior search query of the query log.

34. The system of claim 32, where the candidate string is selected based on whether the count of clicks for the candidate string exceeds a combined count of clicks for the one or more other candidate strings.

35. The system of claim 32, where the entries of the query log include user behavior information and where the candidate string is selected based on the user behavior information.

36. The system of claim 35, where the user behavior information includes whether a conversion occurred associated with the common entity identifier.

37. The system of claim 35, where the user behavior information includes how much time a user spends accessing the common entity identifier.

38. The system of claim 32, where the common entity identifier is a hostname.

39. The system of claim 32, where the common entity identifier is a product identifier.

40. The system of claim 32, where the rewritten search query is used to provide search results to a user.

41. The system of claim 32, where the rewritten search query is used to provide a suggested search query to a user.