Phrase extraction using subphrase scoring

• US 8,166,045 B1
• Filed: 03/30/2007
• Issued: 04/24/2012
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Mazumdar, Soham, Zunger, Yonatan, Przebinda, Viktor
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Singh, Amresh
• Application Number:
  US11/694,792
• Time in Patent Office: 1,852 Days
• Field of Search: 707/748, 707/999.003, 707/999.005, 707/713
• US Class Current: 707/748
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

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 of extracting a set of valid phrases from a plurality of documents, the method comprising:

for each document;

identifying a plurality of candidate phrases contained in the document, wherein a candidate phrase includes multiple consecutive words that appear in the document, wherein identifying a candidate phrase includes scanning though words of the document to identify the multiple consecutive words of the candidate phrase contained in the document;

scoring each candidate phrase in the document to produce a document phrase score for the candidate phrase for the document, the document phrase score being based on each instance of the candidate phrase that appears in the document,

wherein scoring the candidate phrases in the document to produce the document phrase score comprises;

scoring a plurality of instances of the candidate phrase in the document to produce a plurality of instance phrase scores for the candidate phrase for the document, the instance phrase scores being based on a location of the instance of the candidate phrase within the document and being based on a position of the instance of the candidate phrase relative to a sequence of words containing the instance of the candidate phrase; and

combining the plurality of instance phrase scores of the candidate phrase in the document into the document phrase score;

for each candidate phrase;

creating, via a processor, a combined score for the candidate phrase based on a plurality of different document phrase scores for the candidate phrase for respective different documents; and

determining whether the candidate phrase is a valid phrase based on the combined score for the candidate phrase and based on the document phrase scores for the candidate phrase.

2. The method of claim 1, wherein identifying a plurality of candidate phrases contained in the document further comprises:

identifying as a candidate phrase a sequence of words in the document terminated by a semantic marker.

3. The method of claim 2, wherein the semantic marker is any one of group consisting of a linguistic, grammatical, structural, or typographic indicator.

4. The method of claim 1, wherein scoring each candidate phrase in the document to produce a document phrase score further comprises:

determining for each candidate phrase two or more subphrases within the candidate phrase, wherein a subphrase contains two or more words; and

scoring each determined subphrase in the document as a function of the position of the subphrase relative to the sequence of words containing the candidate phrase, and the document phrase score of the candidate phrase.

5. The method of claim 1, wherein scoring each candidate phrase in the document to produce a document phrase score further comprises:

scoring each instance of the candidate phrase in the document to produce an instance phrase score, the instance phrase score being further based on typeface characteristics the instance of the candidate phrase within the document.

6. The method of claim 1, wherein determining whether the candidate phrase is a valid phrase based on the combined score and based on the document phrase scores comprises:

determining a candidate phrase to be valid phrase when a maximum value of the document phrase scores exceeds a first threshold.

7. The method of claim 1, wherein determining whether the candidate phrase is a valid phrase based on the combined score and based on the document phrase scores comprises:

determining a candidate phrase to be valid phrase when the combined score exceeds a second threshold.

8. The method of claim 1, wherein determining whether the candidate phrase is a valid phrase based on the combined score and based on the document phrase scores comprises:

determining a candidate phrase to be valid phrase when the number of documents for which the candidate phrase had at least a minimum document phrase score exceeds a third threshold.

9. The method of claim 1, wherein identifying a plurality of candidate phrases contained in the document further comprises:

identifying as a candidate phrase every sequence of N words, where N is an integer greater than 2.

10. The method of claim 1, wherein determining whether the candidate phrase is a valid phrase based on the combined score and based on the document phrase scores comprises:

determining a candidate phrase to be valid phrase when a maximum value of the document phrase scores exceeds a first threshold, or when the combined score exceeds a second threshold, or when the number of documents for which the candidate phrase had at least a minimum document phrase score exceeds a third threshold.

11. A computer readable medium, having stored thereon, computer program code that, when executed, causes a computer system to extract a set of valid phrases from a plurality of documents, by:

for each document;

identifying a plurality of candidate phrases contained in the document, wherein a candidate phrase includes multiple consecutive words that appear in the document, wherein identifying a candidate phrase includes scanning though words of the document to identify the multiple consecutive words of the candidate phrase;

scoring each candidate phrase in the document to produce a document phrase score for the candidate phrase for the document, the document phrase score being based on each instance of the candidate phrase that appears in the document

wherein scoring the candidate phrases in the document to produce the document phrase score comprises;

scoring a plurality of instances of the candidate phrase in the document to produce a plurality of instance phrase scores for the candidate phrase for the document, the instance phrase scores being based on a location of the instance of the candidate phrase within the document and being based on a position of the instance of the candidate phrase relative to a sequence of words containing the instance of the candidate phrase; and

combining the plurality of instance phrase scores of the candidate phrase in the document into the document phrase score; and

for each candidate phrase;

creating, via a processor of the computer system, a combined score for the candidate phrase based on a plurality of different document phrase scores for the candidate phrase for respective different documents; and

determining whether the candidate phrase is a valid phrase based on the combined score for the candidate phrase and based on the document phrase scores for the candidate phrase.

12. The computer readable medium of claim 11, wherein identifying a plurality of candidate phrases contained in the document further comprises:

identifying as a candidate phrase a sequence of words in the document terminated by a semantic marker.

13. The computer readable medium of claim 12, wherein the semantic marker is any one of group consisting of a linguistic, grammatical, structural, or typographic indicator.

14. The computer readable medium of claim 11, wherein scoring each candidate phrase in the document to produce a document phrase score further comprises:

determining for each candidate phrase two or more subphrases within the candidate phrase, wherein a subphrase contains two or more words; and

scoring each determined subphrase in the document as a function of the position of the subphrase relative to the sequence of words containing the candidate phrase, and the document phrase score of the candidate phrase.

15. The computer readable medium of claim 11, wherein scoring each candidate phrase in the document to produce a document phrase score further comprises:

scoring each instance of the candidate phrase in the document to produce an instance phrase score, the instance phrase score being further based on typeface characteristics the instance of the candidate phrase within the document.

16. The computer readable medium of claim 11, wherein determining whether the candidate phrase is a valid phrase based on the combined score and based on the document phrase scores comprises:

determining a candidate phrase to be valid phrase when a maximum value of the document phrase scores exceeds a first threshold.

17. The computer readable medium of claim 11, wherein determining whether the candidate phrase is a valid phrase based on the combined score and based on the document phrase scores comprises:

determining a candidate phrase to be valid phrase when the combined score exceeds a second threshold.

18. The computer readable medium of claim 11, wherein determining whether the candidate phrase is a valid phrase based on the combined score and based on the document phrase scores comprises:

determining a candidate phrase to be valid phrase when the number of documents for which the candidate phrase had at least a minimum document phrase score exceeds a third threshold.

19. The computer readable medium of claim 11, wherein identifying a plurality of candidate phrases contained in the document further comprises:

identifying as a candidate phrase every sequence of N words, where N is an integer greater than 2.

20. The computer readable medium of claim 11, wherein determining whether the candidate phrase is a valid phrase based on the combined score and based on the document phrase scores comprises:

determining a candidate phrase to be valid phrase when a maximum value of the document phrase scores exceeds a first threshold, or when the combined score exceeds a second threshold, or when the number of documents for which the candidate phrase had at least a minimum document phrase score exceeds a third threshold.