Phrase-based indexing in an information retrieval system

• US 7,536,408 B2
• Filed: 07/26/2004
• Issued: 05/19/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): Vy; Hung T
• Application Number:
  US10/900,055
• Publication Number:
  US 20060020607A1
• Time in Patent Office: 1,758 Days
• Field of Search: 707/1, 707 3- 6, 707/102, 707/104.1, 707/101, 707/9, 704/9, 382/305
• 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

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 method of indexing documents in a document collection, each document having an associated identifier, the method comprising:

providing a list of phrases;

identifying, by operation of a processor adapted to manipulate data within a computer system, for a given document, phrases from the list of phrases that are present in the document;

for each identified phrase in the document;

identifying, by operation of a processor adapted to manipulate data within a computer system, a related phrase also present in the document, wherein for each phrase g_j, g_k is a related phrase of phrase g_j where an information gain I of g_k with respect to g_j exceeds a predetermined threshold, the information gain I being a function of A(j,k) and E(j,k), where A(j,k) is a measure of 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; and

indexing, by operation of a processor adapted to manipulate data within a computer system, the document by storing the identifier of the document and an indication of each related phrase g_k also present in the document, in a posting list of the identified phrase g_j.

2. The method of claim 1, wherein identifying for a given document, phrases from the list of phrases that are present in the document, comprises:

traversing the words of the document with a multiword phrase window.

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

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

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

5. The method of claim 1, wherein storing an indication of each related phrase g_k also present in the document in a posting list of the identified phrase further comprises:

storing, for each related phrase present in the document, said related phrase being a primary related phrase, an indication of at least one secondary related phrase that is a related phrase of the primary related phrase and that is also present in the document.

6. The method of claim 5, wherein the indications of the secondary related phrases are stored in order of decreasing information gain.

7. The method of claim 5, further comprising, for each given document, identifying a primary topic and a secondary topic based upon the identified phrases and related phrases present in the document.

8. The method of claim 1, further comprising, for each identified phrase in the document:

determining whether the identified phrase appears as anchor text for a hyperlink in the document pointing to a target document;

responsive to the identified phrase appearing as anchor text, determining a link score for the identified phrase based upon related phrases of the identified phrase; and

storing the link score in the posting list for the identified phrase and in association with the document.

9. The method of claim 1, further comprising:

storing in the posting list of the phrase a number of related phrases present in the document.

10. A method of indexing documents in a document collection, each document having an associated identifier, the method comprising:

providing a list of valid phrases, wherein each phrase on the list appears a minimum number of times in the document collection, and predicts at least one other phrase, wherein for each phrase g_j, g_k predicts g_j where an information gain I of g_k with respect to g_j exceeds a predetermined threshold, the information gain I being a function of A(j,k) and E(j,k), where A(j,k) is a measure of 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;

accessing a plurality of documents in the document collection;

for each accessed document, identifying, by operation of a processor adapted to manipulate data within a computer system, phrases from the list of valid phrases that are present in the document; and

for each identified phrase in the document, indexing, by operation of a processor adapted to manipulate data within a computer system, the document by storing the identifier of the document in a posting list of the phrase.

11. The method of claim 10, wherein the predetermined threshold is about 1.5.

12. A computer-implemented system for indexing documents in a document collection, each document having an associated identifier, comprising:

a phrase-based index comprising a list of phrases and a plurality of phrase posting lists, each phrase posting list associated with a phrase in the list of phrases; and

an indexing system adapted to;

identify for a given document, phrases from the list of phrases that are present in the document;

for each identified phrase in the document;

identify a related phrase also present in the document, wherein for each phrase g_j, g_k is a related phrase of phrase g_j where an information gain I of g_k with respect to g_j exceeds a predetermined threshold, the information gain I being a function of A(j,k) and E(j,k), where A(j,k) is a measure of 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, and

index the document by storing the identifier of the document and an indication of each related phrase g_k also present in the document, in the phrase-based index, within a posting list associated with the identified phrase.

13. A tangible computer readable storage medium storing a computer program executable by a processor for indexing documents in a document collection, each document having an associated identifier, the operations of the computer program comprising:

providing a list of phrases;

identifying for a given document, phrases from the list of phrases that are present in the document;

for each identified phrase in the document;

identifying a related phrase also present in the document, wherein for each phrase g_j, g_k is a related phrase of phrase g_j where an information gain I of g_k with respect to g_j exceeds a predetermined threshold, the information gain I being a function of A(j,k) and E(j,k), where A(j,k) is a measure of 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, and

indexing the document by storing the identifier of the document and an indication of each related phrase also present in the document, in a posting list of the identified phrase.

14. A computer-implemented system for indexing documents in a document collection, each document having an associated identifier, comprising:

a phrase-based index comprising;

a list of valid phrases, each phrase on the list appearing a minimum number of times in the document collection, and predicting at least one other phrase, wherein for each phrase g_j, g_k predicts g_j where an information gain I of g_k with respect to g_j exceeds a predetermined threshold, the information gain I being a function of A(j,k) and E(j,k), where A(j,k) is a measure of 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, and

a plurality of phrase posting lists, each phrase posting list associated with a phrase in the list of valid phrases; and

an indexing system adapted to;

access a plurality of documents in the document collection,

for each accessed document, identify phrases from the list of valid phrases that are present in the document, and

for each identified phrase in the document, store the identifier of the document in the phrase-based index, within a posting list of the identified phrase.

15. A tangible computer readable storage medium storing a computer program executable by a processor for indexing documents in a document collection, each document having an associated identifier, the operations of the computer program comprising:

providing a list of valid phrases, wherein each phrase on the list appears a minimum number of times in the document collection, and predicts at least one other phrase, wherein for each phrase g_j, g_k predicts g_j where an information gain I of g_k with respect to g_j exceeds a predetermined threshold, the information gain I being a function of A(j,k) and E(j,k), where A(j,k) is a measure of 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;

accessing a plurality of documents in the document collection;

for each accessed document, identifying phrases from the list of valid phrases that are present in the document; and

for each identified phrase in the document, storing the identifier of the document in a posting list of the phrase.

16. A computer-implemented method of indexing a document in an index, the document having an associated identifier, the method comprising:

storing a list of phrases, including related phrases, wherein for each phrase g_j, g_k is a related phrase of phrase g_j where an information gain I of g_k with respect to g_j exceeds a predetermined threshold, the information gain I being a function of A(j,k) and E(j,k), where A(j,k) is a measure of 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;

storing a plurality of phrase posting lists in the index, each phrase posting list associated with a phrase in the list of phrases;

identifying, by operation of a processor adapted to manipulate data within a computer system, a phrase in the list of phrases for which there is at least one instance in the document; and

storing an indication of a related phrase for which there is also an instance in the document, in the phrase posting list of the identified phrase.

17. A method of indexing documents in a document collection, each document having an associated identifier, the method comprising:

providing a list of phrases;

identifying, by operation of a processor adapted to manipulate data within a computer system, for a given document, phrases from the list of phrases that are present in the document;

for each identified phrase in the document;

identifying, by operation of a processor adapted to manipulate data within a computer system, a related phrase also present in the document;

indexing, by operation of a processor adapted to manipulate data within a Computer system, the document by storing the identifier of the document and an indication of each related phrase also present in the document, in a posting list of the identified phrase;

determining, by operation of a processor adapted to manipulate data within a computer system, whether the identified phrase appears as anchor text for a hyperlink in the document pointing to a target document;

responsive to the identified phrase appearing as anchor text, determining a link score for the identified phrase based upon related phrases of the identified phrase; and

storing the link score in the posting list of the identified phrase and in association with the document.

18. The method of claim 17, wherein determining a link score for the identified phrase further comprises:

determining an inlink score based upon related phrases of the identified phrase that are present in the target document.

19. The method of claim 17, wherein determining a link score for the identifier phrase further comprises:

determining an outlink score for the identified phrase based upon related phrases of the identified phrase that are also present in the document.

20. A computer-implemented system for indexing documents in a document collection, each document having an associated identifier, comprising:

a phrase-based index comprising a list of phrases and a plurality of phrase posting lists, each phrase posting list associated with a phrase in the list of phrases; and

an indexing system adapted to;

identify for a given document, phrases from the list of phrases that are present in the document;

for each identified phrase in the document;

identify a related phrase also present in the document,

index the document by storing the identifier of the document and an indication of each related phrase g_k also present in the document, in the phrase-based index, within a posting list associated with the identified phrase

determine whether the identified phrase appears as anchor text for a hyperlink in the document pointing to a target document;

responsive to the identified phrase appearing as anchor text, determine a link score for the identified phrase based upon related phrases of the identified phrase, and

store the link score in the posting list for the identified phrase and in association with the document.