Bifurcated document relevance scoring

• US 8,086,594 B1
• Filed: 03/30/2007
• Issued: 12/27/2011
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cao, Pei, Mazumdar, Soham, Zunger, Yonatan, Mehta, Vaibhav
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Singh, Amresh
• Application Number:
  US11/694,797
• Time in Patent Office: 1,733 Days
• Field of Search: 707/1, 707/5, 707/713
• US Class Current: 707/713
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing

Abstract

An information retrieval system uses phrases to index, retrieve, organize and describe documents. Phrases are extracted from the document collection. Documents are the indexed according to their included phrases, using phrase posting lists. The phrase posting lists are stored in an cluster of index servers. The phrase posting lists can be tiered into groups, and sharded into partitions. Phrases in a query are identified based on possible phrasifications. A query schedule based on the phrases is created from the phrases, and then optimized to reduce query processing and communication costs. The execution of the query schedule is managed to further reduce or eliminate query processing operations at various ones of the index servers.

Claims

1. A computer implemented method for bifurcated document relevance scoring of documents in a document collection, the method comprising:

indexing a plurality of documents in the document collection by;

providing a set of phrases;

for a plurality of documents in the document collection;

identifying a plurality of phrases from the set of phrases that occurs in the document;

for each phrase in a plurality of the identified phrases, scoring the phrase to produce a phrase relevance score for the phrase with respect to the document, and storing the phrase relevance score for the document in a phrase posting list for the phrase;

receiving a search query of three or more words;

determining a set of valid phrases in the search query by;

decomposing, by at least one processor of a computer system, the query into a plurality of candidate phrasifications, including different groupings of words of the query, each candidate phrasification comprising a disjoint union of component phrases, and each component phrase including at least one word or related word of the query;

scoring, by at least one of the processors of the computer system, at least two candidate phrasifications, wherein the candidate phrasifications include one or more component phrases, wherein the scoring is based on a probability of occurrence of each of the candidate phrasification'"'"'s component phrases in a corpus of documents and is based on the number of component phrases constituting the candidate phrasification, wherein candidate phrasifications having relatively fewer component phrases are weighted higher than candidate phrasifications having relatively more component phrases;

comparing, by at least one of the processors of the computer system, a score for each scored candidate phrasification to a threshold value; and

selecting, by at least one of the processors of the computer system, at least one candidate phrasification, wherein the scores of each selected candidate phrasification exceed a threshold value and identifying the component phrase(s) of the selected candidate phrasification(s) as valid phrases for the search query;

for each valid phrase for the search query, obtaining from the phrase posting list for the valid phrase the phrase relevance score for documents in which the valid phrase occurs; and

for documents in which a valid phrase of the query occurs, scoring the document to produce a final relevance score using the phrase relevance scores for the document and based on the valid phrases of the search query.

2. The method of claim 1, wherein:

scoring the phrase to produce a phrase relevance score for the phrase with respect to the document comprises scoring the phrase and the document using a first scoring function; and

scoring the document to produce a final relevance score using the phrase relevance scores for the document comprises scoring the document using a second scoring function.

3. A computer implemented method of bifurcated document relevance scoring of documents in a document collection, the method comprising:

storing an index of documents, the index comprising;

for each of a plurality of phrases, a phrase posting list identifying the documents that contain the phrase, and for each identified document, a phrase relevance score for the phrase with respect to the document;

receiving a search query of three or more words;

determining a set of valid phrases in the search query by;

decomposing, by at least one processor of a computer system, the query into a plurality of candidate phrasifications, including different groupings of words of the query, each candidate phrasification comprising a disjoint union of component phrases, and each component phrase including at least one word or related word of the query;

scoring, by at least one of the processors of the computer system, at least two candidate phrasifications, wherein the candidate phrasifications include one or more component phrases, wherein the scoring is based on a probability of occurrence of each of the candidate phrasification'"'"'s component phrases in a corpus of documents and is based on the number of component phrases constituting the candidate phrasification, wherein candidate phrasifications having relatively fewer component phrases are weighted higher than candidate phrasifications having relatively more component phrases;

comparing, by at least one of the processors of the computer system, a score for each scored candidate phrasification to a threshold value; and

selecting, by at least one of the processors of the computer system, at least one candidate phrasification, wherein the scores of each selected candidate phrasification exceed a threshold value and identifying the component phrase(s) of the selected candidate phrasification(s) as valid phrases for the search query;

for each valid phrase for the search query, obtaining from the phrase posting list for the valid phrase the phrase relevance score for documents in which the valid phrase occurs; and

for documents in which a valid phrase of the query occurs, scoring the document to produce a final relevance score using the phrase relevance scores for the document and based on the valid phrases of the search query.

4. The method of claim 3, further comprising:

indexing the plurality of documents in the document collection by;

for each document in the document collection;

identifying each phrase from the set of phrases that occurs in the document;

for each identified phrase, scoring the phrase to produce a phrase relevance score for the phrase with respect to the document, and storing the phrase relevance score for the document in a phrase posting list for the phrase.

5. The method of claim 3, wherein the posting lists for the phrases store information consisting of only a document identifier of a current document and the phrase relevance score for the phrase with respect to the document.

6. The method of claim 3, further comprising updating the posting list for the identified phrases to indicate the documents for which the phrases are identified, and information about the significance of the phrase to the documents.

7. A computer program product stored on a computer readable medium and comprising instructions that when executed cause a computer system to:

index a plurality of documents in the document collection by;

providing a set of phrases;

for a plurality of documents in the document collection;

identifying a plurality of phrases from the set of phrases that occurs in the document;

for a plurality of the identified phrases, scoring the phrase to produce a phrase relevance score for the phrase with respect to the document, and storing the phrase relevance score for the document in a phrase posting list for the phrase;

receive a search query of three or more words;

determining a set of valid phrases in the search query by;

decomposing, by at least one processor of a computer system, the query into a plurality of candidate phrasifications, including different groupings of words of the query, each candidate phrasification comprising a disjoint union of component phrases, and each component phrase including at least one word or related word of the query;

scoring, by at least one of the processors of the computer system, at least two candidate phrasifications, wherein the candidate phrasifications include one or more component phrases, wherein the scoring is based on a probability of occurrence of each of the candidate phrasification'"'"'s component phrases in a corpus of documents and is based on the number of component phrases constituting the candidate phrasification, wherein candidate phrasifications having relatively fewer component phrases are weighted higher than candidate phrasifications having relatively more component phrases;

comparing, by at least one of the processors of the computer system, a score for each scored candidate phrasification to a threshold value; and

selecting, by at least one of the processors of the computer system, at least one candidate phrasification, wherein the scores of each selected candidate phrasification exceed a threshold value and identifying the component phrase(s) of the selected candidate phrasification(s) as valid phrases for the search query;

for each valid phrase for the search query, obtaining from the phrase posting list for the valid phrase the phrase relevance score for documents in which the valid phrase occurs; and

for documents in which a valid phrase of the query occurs, scoring the document to produce a final relevance score using the phrase relevance scores for the document and based on the valid phrases of the search query.

8. The computer program product of claim 7, wherein:

scoring the phrase to produce a phrase relevance score for the phrase with respect to the document comprises scoring the phrase and the document using a first scoring function; and

scoring the document to produce a final relevance score using the phrase relevance scores for the document comprises scoring the document using a second scoring function.

9. A computer program product stored on a tangible computer readable medium and comprising instructions that when executed cause a computer system to:

store an index of documents, the index comprising;

for each of a plurality of phrases, a phrase posting list identifying the documents that contain the phrase, and for each identified document, a phrase relevance score for the phrase with respect to the document;

receive a search query of three or more words;

determine a set of valid phrases in the search query by;

decomposing, by at least one processor of a computer system, the query into a plurality of candidate phrasifications, including different groupings of words of the query, each candidate phrasification comprising a disjoint union of component phrases, and each component phrase including at least one word or related word of the query;

scoring, by at least one of the processors of the computer system, at least two candidate phrasifications, wherein the candidate phrasifications include one or more component phrases, wherein the scoring is based on a probability of occurrence of each of the candidate phrasification'"'"'s component phrases in a corpus of documents and is based on the number of component phrases constituting the candidate phrasification, wherein candidate phrasifications having relatively fewer component phrases are weighted higher than candidate phrasifications having relatively more component phrases;

comparing, by at least one of the processors of the computer system, a score for each scored candidate phrasification to a threshold value; and

selecting, by at least one of the processors of the computer system, at least one candidate phrasification, wherein the scores of each selected candidate phrasification exceed a threshold value and identifying the component phrase(s) of the selected candidate phrasification(s) as valid phrases for the search query;

for each valid phrase for the search query, obtaining from the phrase posting list for the valid phrase the phrase relevance score for documents in which the valid phrase occurs; and

for documents in which a valid phrase of the query occurs, scoring the document to produce a final relevance score using the phrase relevance scores for the document and based on the valid phrases of the search query.

10. The computer program product of claim 9, further comprising instructions that when executed cause the computer system to:

index the plurality of documents in the document collection by;

for each document in the document collection;

identifying each phrase from the set of phrases that occurs in the document;

for each identified phrase, scoring the phrase to produce a phrase relevance score for the phrase with respect to the document, and storing the phrase relevance score for the document in a phrase posting list for the phrase;

for each phrase in the search query, obtaining the phrase relevance score for each document in which the phrase occurs from the phrase posting list; and

for each document in which a phrase of the query occurs, scoring the document to produce a final relevance score using the phrase relevance scores for the document and the search query.

11. The computer program product of claim 9, wherein the posting lists for the phrases store information consisting of only a document identifier of a current document and the information retrieval score for the phrase with respect to the document.

12. The computer program product of claim 9, further comprising instructions that when executed cause the computer system to update the posting list for the identified phrases to indicate the documents for which the valid phrases are identified, and information about the significance of the valid phrase to the documents.

13. A system for bifurcated document relevance scoring of documents in a document collection, the system comprising:

an indexing system configured for indexing a plurality of documents in the document collection, the indexing system comprising;

one or more memories configured for storing a set of phrases; and

one or more processors configured for;

for a plurality of documents in the document collection, identifying a plurality of phrases from the set of phrases that occurs in the document; and

for each phrase in a plurality of the identified phrases, scoring the phrase to produce a phrase relevance score for the phrase with respect to the document, and storing the phrase relevance score for the document in a phrase posting list for the phrase;

a search system comprising;

a first server configured for receiving a search query of three or more words; and

one or more processors configured for;

decomposing, by at least one processor of a computer system, the query into a plurality of candidate phrasifications, including different groupings of words of the query, each candidate phrasification comprising a disjoint union of component phrases, and each component phrase including at least one word or related word of the query;

scoring, by at least one of the processors of the computer system, at least two candidate phrasifications, wherein the candidate phrasifications include one or more component phrases, wherein the scoring is based on a probability of occurrence of each of the candidate phrasification'"'"'s component phrases in a corpus of documents and is based on the number of component phrases constituting the candidate phrasification, wherein candidate phrasifications having relatively fewer component phrases are weighted higher than candidate phrasifications having relatively more component phrases;

comparing, by at least one of the processors of the computer system, a score for each scored candidate phrasification to a threshold value; and

selecting, by at least one of the processors of the computer system, at least one candidate phrasification, wherein the scores of each selected candidate phrasification exceed a threshold value and identifying the component phrase(s) of the selected candidate phrasification(s) as valid phrases for the search query;

for each valid phrase for the search query, obtaining from the phrase posting list for the valid phrase the phrase relevance score for documents in which the valid phrase occurs; and

for documents in which a valid phrase of the query occurs, scoring the document to produce a final relevance score using the phrase relevance scores for the document and based on the valid phrases of the search query.

14. The system of claim 13, wherein:

scoring the phrase to produce a phrase relevance score for the phrase with respect to the document comprises scoring the phrase and the document using a first scoring function; and

scoring the document to produce a final relevance score using the phrase relevance scores for the document comprises scoring the document using a second scoring function.

15. A system for bifurcated document relevance scoring of documents in a document collection, the system comprising:

one or more memories configured for storing an index of documents, the index comprising, for each of a plurality of phrases, a phrase posting list identifying the documents that contain the phrase, and for each identified document, a phrase relevance score for the phrase with respect to the document;

a search server comprising;

a first server configured for receiving a search query of three or more words;

one or more processors configured for determining a set of valid phrases in the search query by;

decomposing, by at least one processor of a computer system, the query into a plurality of candidate phrasifications, including different groupings of words of the query, each candidate phrasification comprising a disjoint union of component phrases, and each component phrase including at least one word or related word of the query;

scoring, by at least one of the processors of the computer system, at least two candidate phrasifications, wherein the candidate phrasifications include one or more component phrases, wherein the scoring is based on a probability of occurrence of each of the candidate phrasification'"'"'s component phrases in a corpus of documents and is based on the number of component phrases constituting the candidate phrasification, wherein candidate phrasifications having relatively fewer component phrases are weighted higher than candidate phrasifications having relatively more component phrases;

comparing, by at least one of the processors of the computer system, a score for each scored candidate phrasification to a threshold value; and

selecting, by at least one of the processors of the computer system, at least one candidate phrasification, wherein the scores of each selected candidate phrasification exceed a threshold value and identifying the component phrase(s) of the selected candidate phrasification(s) as valid phrases for the search query;

for each valid phrase for the search query, obtaining from the phrase posting list for the valid phrase the phrase relevance score for documents in which the valid phrase occurs; and

for documents in which a valid phrase of the query occurs, scoring the document to produce a final relevance score using the phrase relevance scores for the document and based on the valid phrases of the search query.

16. The system of claim 15, further comprising:

an indexing system including one or more processors configured for indexing the plurality of documents in the document collection by, for each document in the document collection;

identifying each phrase from the set of phrases that occurs in the document;

for each identified phrase, scoring the phrase to produce a phrase relevance score for the phrase with respect to the document, and storing the phrase relevance score for the document in a phrase posting list for the phrase.

17. The system of claim 15, wherein the posting lists for the phrases store information consisting of only a document identifier of a current document and the phrase relevance score for the phrase with respect to the document.

18. The system of claim 15, wherein the one or more processors are further configured for updating the posting list for the identified phrases to indicate the documents for which the phrases are identified, and information about the significance of the phrase to the documents.