Phrase identification in an information retrieval system

• US 7,580,921 B2
• Filed: 07/26/2004
• Issued: 08/25/2009
• Est. Priority Date: 07/26/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Patterson, Anna Lynn
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): CAO, PHUONG THAO
• Application Number:
  US10/900,021
• Publication Number:
  US 20060018551A1
• Time in Patent Office: 1,856 Days
• Field of Search: 707 1- 3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• 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/99937 Sorting

Abstract

An information retrieval system uses phrases to index, retrieve, organize and describe documents. Phrases are identified that predict the presence of other phrases in documents. Documents are the indexed according to their included phrases. Related phrases and phrase extensions are also identified. Phrases in a query are identified and used to retrieve and rank documents. Phrases are also used to cluster documents in the search results, create document descriptions, and eliminate duplicate documents from the search results, and from the index.

Claims

1. A computer implemented method for identifying phrases in a document collection, the method comprising:

collecting possible phrases from documents in the document collection;

classifying individual possible phrases as either a good phrase or a bad phrase according to a frequency of occurrence of the individual possible phrase;

determining, for a pair of good phrases g_j and g_k in the document collection, an information gain of g_k with respect to g_j as a function of an actual co-occurrence rate of g_j and g_k and an expected co-occurrence rate of g_j and g_k in the document collection;

selectively retaining as valid phrases those good phrases that, predict the occurrence of at least one other good phrase in the document collection, where a good phrase g_j predicts the occurrence of another good phrase g_k in the document collection when the determined information gain of g_k in the presence of g_j exceeds a first predetermined threshold;

identifying, for a plurality of selectively retained valid phrases g_x, a phrase g_y as a related phrase of g_x where the information gain of g_y in the presence of g_x exceeds a second predetermined threshold that is more restrictive than the first predetermined threshold; and

storing the valid phrases and identified related phrases on a computer-readable storage medium.

2. The method of claim 1, wherein collecting possible phrases comprises:

traversing the words of a document with a multiword phrase window, and selecting as candidate phrases all sequences of words in the window that begin with a first word in the window.

3. The method of claim 2, wherein the phrase window includes at least 4 words.

4. The method of claim 1, wherein collecting possible phrases comprises:

maintaining for each possible phrase and each good phrase a frequency count of a number of documents containing the phrase;

maintaining for each possible phrase and each good phrase a frequency count of a number of instances of the phrase; and

maintaining for each possible phrases and each good phrase a frequency count of a number of distinguished instances of the phrase.

5. The method of claim 4, wherein a distinguished instance of a phrase comprises a phrase distinguished from neighboring content in the document by grammatical or format markers.

6. The method of claim 1, wherein classifying each possible phrase as either a good phrase or a bad phrase comprises:

classifying a possible phrase as a good phrase where the possible phrase appears in a minimum number of documents, and appears a minimum number of instances in the document collection.

7. The method of claim 1, wherein classifying each possible phrase as either a good phrase or a bad phrase comprises:

classifying a possible phrase as a good phrase where the possible phrase appears in a minimum number of distinguished instances in the document collection.

8. The method of claim 1, wherein the first predetermined threshold is 1.

9. The method of claim 1, wherein the information gain of g_j with respect to g_k is:

I(j,k)=A(j,k)/E(j,k)

where

A(j,k) is an actual co-occurrence rate of g_j and g_k; and

E(j,k) is an expected co-occurrence rate g_j and g_k.

10. The method of claim 9, wherein good phrases g_j and g_k co-occur in a document when g_j and g_k are within a predetermined number of words of each other.

11. The method of claim 1, wherein retaining good phrases that predict the occurrence of at least one other good phrase in the document collection comprises:

removing a good phrase having an information gain with respect to a plurality of other good phrases less than a predetermined threshold.

12. The method of claim 1, further comprising:

removing incomplete phrases from the good phrases.

13. The method of claim 12, wherein an incomplete phrase is a phrase that only predicts its phrase extensions, and wherein a phrase extension of a phrase is a super-sequence of the phrase that begins with the phrase.

14. The method of claim 12, further comprising:

maintaining for each incomplete phrase at least one phrase extension of the incomplete phrase; and

responsive to a phrase in a search query being an incomplete phrase, including in the search query at least one phrase extension of the incomplete search phrase.

15. The method of claim 1, wherein the second predetermined threshold is about 100.

16. The method of claim 1, further comprising:

for each phrase g_x, identifying a cluster comprising the phrase and at least one related phrase g_y.

17. The method of claim 1, further comprising:

for each phrase g_x, identifying a set R including a plurality of related phrases;

determining for each pair of related phrases in set R an information gain of the pair of related phrases; and

identifying as a cluster of related phrases of g_x, phrase g_x, and each related phrase in set R that has non-zero information gain with respect to each other phrase in set R.

18. The method of claim 17, further comprising:

assigning each cluster a unique cluster number as a function of the related phrases included in the cluster.

19. The method of claim 17, further comprising:

assigning to the cluster a name comprising the related phrase having a highest information gain of the related phrases in the cluster.

20. The method of claim 1, further comprising:

for a phrase g_j, storing a bit vector in which each bit position corresponds to a valid phrase, and the bit corresponding to the bit position indicates whether the valid phrase is a related phrase of g_j.

21. A computer program product, for identifying phrases in a document collection, comprising computer operable instructions stored on a computer-readable storage medium and configured to control a processor to perform the operation of:

collecting possible phrases from documents in the document collection;

classifying individual possible phrases as either a good phrase or a bad phrase according to a frequency of occurrence of the possible phrase;

determining, for a pair of good phrases g_j and g_k in the document collection, an information gain of g_k with respect to g_j as a function of an actual co-occurrence rate of g_j and g_k and an expected co-occurrence rate of g_j and g_k in the document collection;

selectively retaining as valid phrases those good phrases that predict the occurrence of at least one other good phrase in the document collection, where a good phrase g_j predicts the occurrence of another good phrase g_k in the document collection when the determined information gain of g_k in the presence of g_j exceeds a first predetermined threshold;

identifying, for a plurality of selectively retained valid phrases g_x, a phrase g_y as a related phrase of g_x where the information gain of g_y in the presence of g_x exceeds a second predetermined threshold that is more restrictive than the first predetermined threshold; and

storing the selectively retained good phrases on a computer-readable storage medium.

22. The computer program product of claim 21, wherein the information gain of g_j with respect to g_k is defined as I(j,k)=A(j,k)/E(j,k), where A(j,k) is an actual co-occurrence rate of g_j and g_k, and E(j,k) is an expected co-occurrence rate of g_j and g_k.

23. A computer implemented method for indexing documents in a document collection, the method comprising:

collecting possible phrases from documents in the document collection;

classifying each possible phrase as either a good phrase or a bad phrase according to a frequency of occurrence of the possible phrase;

determining, for a pair of good phrases g_j and g_k in the document collection, an information gain of g_k with respect to g_j as a function of an actual co-occurrence rate of g_j and g_k and an expected co-occurrence rate of g_j and g_k in the document collection;

storing as valid phrases, on a computer-readable storage medium, only good phrases that predict the occurrence of at least one other good phrase in the document collection where a good phrase g_j predicts the occurrence of another good phrase g_k in the document collection when the determined information gain of g_k in the presence of g_j exceeds a first predetermined threshold;

identifying, for a plurality of selectively retained valid phrases g_x, a phrase g_y as a related phrase of g_x where the information gain of g_y in the presence of g_x exceeds a second predetermined threshold that is more restrictive than the first predetermined threshold; and

indexing documents in the document collection with respect to the valid phrases and the related phrases.

24. The method of claim 23, wherein the information gain of g_k with respect to g_j is defined as I(j,k)=A(j,k)/E(j,k), where A(j,k) is an actual co-occurrence rate of g_j and g_k, and E(j,k) is an expected co-occurrence rate of g_j and g_k.

25. The method of claim 23, wherein collecting possible phrases comprises:

maintaining for each possible phrase and each good phrase a frequency count of a number of documents containing the phrase;

maintaining for each possible phrase and each good phrase a frequency count of a number of instances of the phrase; and

maintaining for each possible phrases and each good phrase a frequency count of a number of distinguished instances of the phrase, a distinguished instance of the phrase comprising the phrase distinguished from neighboring content in the document by grammatical or format markers.