Methods and apparatus for determining equivalent descriptions for an information need

• US 6,941,293 B1
• Filed: 02/01/2002
• Issued: 09/06/2005
• Est. Priority Date: 02/01/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Dean, Jeffrey A., Harik, Georges, Shazeer, Noam, Gomes, Benedict
• Primary Examiner(s): Coby, Frantz
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US10/062,110
• Time in Patent Office: 1,313 Days
• Field of Search: 707/3, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Methods and apparatus determine equivalent descriptions for an information need. In one implementation, if adjacent entries in a query log contain common terms, the uncommon terms are identified as a candidate pair. The candidate pairs are assigned a score based on their frequency of occurrence, and pairs having a score exceeding a defined threshold are determined to be synonyms.

Claims

1. A computer-implemented method for determining equivalent descriptions for an information need, comprising:

identifying a list of queries issued by one or more users;

identifying a candidate pair of equivalent descriptions by locating two queries that refer to the same information need;

calculating a score for the candidate pair dependent on the frequency with which the candidate pair occurs in the list; and

determining that each half of the candidate pair is an equivalent description for the information need if the score calculated for the candidate pair is above a defined threshold value.

2. The computer-implemented method of claim 1, wherein identifying a candidate pair comprises:

locating two queries that contain at least one term in common; and

identifying as a candidate pair the portions of the two queries that are not in common.

3. The computer-implemented method of claim 1, wherein identifying a candidate pair comprises:

identifying, in a first description, a term T1 having characters C_i, where i=1 through n;

identifying, in a second description, a sequence of n terms, T2₁, T2₂ . . . T2_n; and

determining that term T1 and terms T2₁, T2₂ . . . T2_n are a candidate pair if each C_i matches the first letter of T2_i.

4. The computer-implemented method of claim 1, wherein calculating a score comprises:

determining a first frequency with which the candidate pair occurs within the list;

determining a second frequency with which one half of the candidate pair occurs within the list; and

calculating a score based on a ratio of the first frequency and the second frequency.

5. The computer-implemented method of claim 1, further comprising excluding any candidate pair with a frequency of occurrence in the list below a defined threshold.

6. The computer-implemented method of claim 1, further comprising excluding any candidate pair wherein one half of the candidate pair contains a misspelled term.

7. The computer-implemented method of claim 1, further comprising excluding any candidate pair wherein it is determined that one half of the candidate pair is an alternative rather than an equivalent for the second half of the candidate pair.

8. The computer-implemented method of claim 7, wherein the determination comprises:

locating a collection of documents;

identifying lists within the collection, wherein each list contains both halves of the candidate pair; and

determining that one half of the candidate pair is an alternative for the second half based on the frequency with which each half occurs in the lists.

26. The computer-implemented method of claim 1 wherein the list of queries is a list of previously submitted search queries.

9. The computer-implemented method for determining equivalent descriptions for an information need, comprising:

identifying a plurality of descriptions that are associated with a plurality of information needs;

identifying a candidate pair of equivalent descriptions by locating two descriptions that refer to the same information need;

calculating a score for the candidate pair dependent on the frequency with which the candidate pair occurs in the plurality of descriptions; and

determining that each of the candidate pair is an equivalent description for the information need if the score is above a defined threshold.

10. The computer-implemented method of claim 9 wherein the plurality of descriptions comprises an historical log of user queries.

11. The computer-implemented method of claim 10, further comprising sorting the log by user.

12. The computer-implemented method of claim 11, further comprising sorting the log by the time when the query was issued.

13. The computer-implemented method of claim 9 wherein identifying a candidate pair comprises:

identifying two descriptions that contain a common term; and

identifying as a candidate pair the terms not in common between the two descriptions.

14. The computer-implemented method of claim 9 wherein identifying a candidate pair comprises:

comparing each letter of a term in a first description against the corresponding first letter of terms in a second description; and

determining, based on the comparison, that the term in the first description and the corresponding terms in the second description are a candidate pair.

15. The computer-implemented method of claim 9 wherein calculating a score comprises:

determining a first frequency with which the candidate pair occurs within the plurality of descriptions;

determining a second frequency with which one half of the candidate pair occurs within the plurality of descriptions; and

calculating a score based on a ratio of the first frequency and the second frequency.

16. The computer-implemented method of claim 9 wherein calculating a score comprises:

determining a first frequency with which the candidate pair occurs within the plurality of descriptions;

determining a second frequency with which one half of the candidate pair occurs within the plurality of descriptions;

determining a third frequency with which the other half of the candidate pair occurs within the plurality of descriptions;

calculating a score bases on a ratio of the first frequency and the smaller of the second and third frequencies.

17. A computer-implemented method for determining synonyms, comprising:

obtaining a list of search queries issued by one or more users;

sorting the list first by user and second by the time when the query was issued;

selecting a set of adjacent queries for a single user;

identifying, from the set, two queries that contain at least one query term in common;

identifying as a candidate synonym pair the uncommon portions of the two queries;

calculating a score for candidate synonym pair dependent on the frequency with which the candidate synonym pair occurs in the list; and

determining that each half of the candidate synonym pair is a synonym of the other half if the score is above a defined threshold.

18. The computer-implemented method of claim 17, wherein calculating a score comprises:

determining a first frequency with which the candidate synonym pair occurs within the list;

determining a second frequency with which one half of the candidate pair occurs within the list; and

calculating a score based on a ratio of the first frequency and the second frequency.

19. The computer-implemented method of claim 17, further comprising excluding any candidate synonym pair with a frequency of occurrence below a defined threshold.

20. The computer-implemented method of claim 17, further comprising excluding any candidate synonym pair wherein one half of the candidate synonym pair contains a misspelled term.

21. The computer-implemented method of claim 17, further comprising excluding any candidate synonym pair wherein it is determined that one half of the candidate synonym pair is an alterative rather than an equivalent for the second half of the candidate synonym pair.

22. The computer-implemented method of claim 21, wherein the determination comprises:

locating a collection of documents;

identifying lists within the collection, wherein each list contains both halves of the candidate synonym pair; and

determining that one half of the candidate synonym pair is an alternative for the second half based on the frequency with which each half occurs in the lists.

23. A computer-implemented method for determining equivalent descriptions for an information need, comprising:

creating a list of anchor text units;

determining a subset of the list that refers to the same information need;

locating, within the subset, two anchor text units that contain at least one term in common;

identifying as a candidate pair of equivalent descriptions the uncommon portions of the two anchor text units;

calculating a score for the candidate pair dependent on the frequency with which the candidate pair occurs in the list; and

determining that each half of the candidate pair is an equivalent description for the information need if the score is above a defined threshold.

24. An apparatus for determining equivalent descriptions for an information need, comprising:

means for identifying a list of queries issued by one or more users;

means for identifying a candidate pair of equivalent descriptions by locating two queries that refer to the same information need;

means for calculating a score for the candidate pair dependent on the frequency with which the candidate pair occurs in the list; and

means for determining that each half of the candidate pair is an equivalent description for the information need if the score id above a defined threshold.

25. An apparatus for determining equivalent descriptions for an information need, comprising:

at least one memory having program instructions, and

at least one processor configured to execute the program instructions to perform the operations of;

identifying a list of queries issued by one or more users;

identifying a candidate pair of equivalent descriptions by locating two queries that refer to the same information need;

calculating a score for the candidate pair dependent in the frequency with which the candidate pair occurs in the list; and

determining that each half of the candidate pair is an equivalent description for the information need if the score is above a defined threshold.

27. The apparatus of claim 25 wherein the list of queries is a list of previously submitted search queries.