Determining query term synonyms within query context

• US 7,636,714 B1
• Filed: 03/31/2005
• Issued: 12/22/2009
• Est. Priority Date: 03/31/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baker, Steven, Lamping, John
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): MENG, JAU SHYA
• Application Number:
  US11/096,726
• Time in Patent Office: 1,727 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method is applied to search terms for determining synonyms or other replacement terms used in an information retrieval system. User queries are first sorted by user identity and session. For each user query, a plurality of pseudo-queries is determined, each pseudo-query derived from a user query by replacing a phrase of the user query with a token. For each phrase, at least one candidate synonym is determined. The candidate synonym is a term that was used within a user query in place of the phrase, and in the context of a pseudo-query. The strength or quality of candidate synonyms is evaluated. Validated synonyms may be either suggested to the user or automatically added to user search strings.

Claims

1. A computer-implemented method of searching for information in an information retrieval system, the computer-implemented method comprising:

receiving a search query comprising a plurality of terms;

selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query;

selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query;

deriving an altered query by replacing the selected term in the received query with a disjunction of the selected term and the replacement term; and

generating a list of search results for the altered query.

2. The computer-implemented method of claim 1, further comprising:

analyzing query logs containing the previously received multi-term queries, to identify;

a first plurality of multi-term search queries in which a first term appears in context with a set of other terms;

a second plurality of multi-term search queries in which a second term appears in the context with the set of other terms; and

storing in a memory the second term as a synonym for the first term in the context of the set of other terms.

3. The computer-implemented method of claim 2, wherein analyzing the query logs comprises:

identifying a pair of multi-term queries in the query logs, wherein a first multi-term query of the pair includes a first phrase in a relative position within the first multi-term query and a second multi-term query of the pair includes a second phrase in the relative position within the second multi-term query;

determining a number of search results that are common to the pair of multi-term queries; and

identifying the first phrase as synonymous with the second phrase in the context of the received query in response to the number of search results that are common to the pair of multi-term queries exceeding a threshold.

4. The computer-implemented method of claim 1, wherein selecting a replacement term comprises:

identifying multi-term query pairs in stored data;

analyzing information corresponding to the multi-term query pairs;

selecting a subset of the multi-term query pairs for which the second queries of the multi-term query pairs include candidate replacement terms for a phrase in the first queries of the multi-term query pairs; and

ranking the candidate replacement terms.

5. The computer-implemented method of claim 4, wherein the information includes evidence as to whether a phrase in the multi-term search query and a phrase in the altered query are synonymous.

6. The computer-implemented method of claim 5, wherein the evidence includes a frequency with which one of the multi-term query pairs occurs within a predetermined time interval.

7. The computer-implemented method of claim 6, wherein the predetermined time interval occurs within a single user session.

8. The computer-implemented method of claim 5, wherein the evidence includes quantity information about top results shared by the multi-term search query and the altered query.

9. The computer-implemented method of claim 4, wherein the information includes evidence as to whether a phrase in the multi-term search query and a phrase in the altered query are synonymous.

10. The computer-implemented method of claim 1, further comprising:

identifying a pair of multi-term queries in the query logs, wherein a first multi-term query of the pair includes a first phrase in a particular relative position within the first multi-term query and a second multi-term query of the pair includes a second phrase in the particular relative position within the second multi-term query;

determining a number of search results that are common to the pair of multi-term queries; and

identifying the first phrase as synonymous with the second phrase in the context of the received multi-term query in response to the number of search results that are common to the pair of multi-term queries exceeding a threshold.

11. A computer-implemented method of searching for information in an information retrieval system, the computer-implemented method comprising:

receiving a search query comprising a plurality of terms;

generating search results for the search query;

selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query;

selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries of as the position of the selected term relative to the remaining unselected terms of the received search query;

providing a ranking of the search results; and

modifying the ranking of the search results based on whether the search results include the replacement term.

12. A computer-implemented method of searching for information in an information retrieval system, the computer-implemented method comprising:

receiving a search query comprising a plurality of terms;

generating a list of search results for the search query;

selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query;

selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query;

deriving an altered query by replacing the selected term in the received query with a disjunction of the selected term and the replacement term; and

generating a list of altered search results for the altered query.

13. A computer program product for searching for information in an information retrieval system, the computer program product comprising:

a computer-readable storage medium; and

computer program code, coded on the medium, for;

receiving a search query comprising a plurality of terms;

generating a list of search results for the search query;

selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query;

selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query;

deriving an altered query by replacing the selected term in the received query with a disjunction of the selected term and the replacement term; and

generating a list of altered search results for the altered query.

14. A computer program product for searching for information in an information retrieval system, the computer program product comprising:

a computer-readable storage medium; and

computer program code, coded on the medium, for;

receiving a search query comprising a plurality of terms;

selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query;

selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query;

deriving an altered query by replacing the selected term in the received query with a disjunction of the selected term and the replacement term; and

generating a list of search results for the altered query.

15. A computer program product for determining synonyms for search query terms, the computer program product comprising:

a computer-readable storage medium; and

computer program code, coded on the medium, for;

receiving a search query comprising a plurality of terms;

generating a list of search results for the search query;

selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query;

selecting, for the selected term, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query;

providing a ranking of the search results; and

modifying the ranking of the search results based on whether the search results include the replacement term.

16. A computer-implemented method of searching for information in an information retrieval system, the computer-implemented method comprising:

receiving a search query comprising a plurality of terms;

selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query;

selecting, for the selected terms, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query;

deriving an altered query by replacing the selected terms in the received query with the replacement term; and

generating a list of search results for the altered query.

17. The computer-implemented method of claim 16, further comprising:

analyzing query logs containing the previously received multi-term queries, to identify;

a first plurality of multi-term search queries in which a first term appears in context with a set of other terms;

a second plurality of multi-term search queries in which a second term appears in the context with the set of other terms; and

storing in a memory the second term as a synonym for the first term in the context of the set of other terms.

18. The computer-implemented method of claim 16, wherein selecting a replacement term comprises:

identifying multi-term query pairs in stored data;

analyzing information corresponding to the multi-term query pairs;

selecting a subset of the multi-term query pairs for which the second queries of the multi-term query pairs include candidate replacement terms for a phrase in the first queries of the multi-term query pairs; and

ranking the candidate replacement terms.

19. A computer program product for searching for information in an information retrieval system, the computer program product comprising:

a computer-readable storage medium; and

computer program code, coded on the medium, for;

receiving a search query comprising a plurality of terms;

selecting one of the plurality of terms, wherein unselected terms of the plurality of terms comprise remaining terms of the received search query and the selected term has a position relative to the remaining unselected terms of the received search query;

selecting, for the selected terms, a replacement term that appears in a plurality of previously received multi-term search queries in a same position within the previously received multi-term search queries as the position of the selected term relative to the remaining unselected terms of the received search query;

deriving an altered query by replacing the selected terms in the received query with the replacement term; and

generating a list of search results for the altered query.