Phrase-based generation of document descriptions

• US 7,584,175 B2
• Filed: 07/26/2004
• Issued: 09/01/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,075
• Publication Number:
  US 20060020571A1
• Time in Patent Office: 1,863 Days
• Field of Search: 707/1, 707 3- 6, 704/1, 704/9, 715/531, 715/530
• US Class Current: 1/1
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

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 automatically generating a description of a document, the method comprising:

retrieving a document in response to a query, the query comprising a query phrase, the document including a plurality of sentences;

calculating, by operation of a processor adapted to manipulate data within a computer system, for sentences of the document, a first count that includes a measure of a number of instances in which the query phrase occurs in the sentences;

calculating, by operation of a processor adapted to manipulate data within a computer system, for sentences of the document, a second count that includes a measure of a number of instances in which any of one or more related phrases of the query phrase occurs in the sentences;

calculating, by operation of a processor adapted to manipulate data within a computer system, for sentences of the document, a third count that includes a measure of a number of instances in which any of one or more phrase extensions of the query phrase occurs in the sentences, wherein a phrase extension is a super-sequence that begins with the query phrase;

selecting one or more of the sentences of the document based on their respective first, second and third counts; and

forming a description of the document from the selected sentences, wherein a phrase g_j is a related phrase of another phrase g_k where an information gain of g_j with respect to g_k exceeds a predetermined threshold, the information gain being a function of both actual and expected co-occurrence rates of g_j and g_k.

2. The method of claim 1, wherein selecting the one or more of the sentences of the document based on their respective first, second and third counts, comprises:

sorting the sentences of the document in declining order of their respective counts; and

selecting a number of the sentences of the document having the highest counts.

3. The method of claim 2, wherein sorting the sentences of the document in declining order of their respective counts, comprises:

the first count of the query phrase constituting a primary sort key;

the second count constituting a secondary sort key; and

the third count constituting a tertiary sort key.

4. The method claim 1, wherein forming a description of the document from the selected sentences, comprises concatenating the selected sentences to form a block of text.

5. The method claim 1, wherein identifying related phrases of the query phrase in a sentence comprises reading a related phrase bit vector of the query phrase, the related phrase bit vector having an ordered set of bits, each bit indicating whether a corresponding related phrase is present in a given document.

6. A tangible computer readable storage medium storing a computer program executable by a processor for automatically generating a description of a document, the operations of the computer program comprising:

retrieving a document in response to a query, the query comprising a query phase, the document including a plurality of sentences;

calculating for sentences of the document, a first count that includes a measure of a number of instances in which the query phrase occurs in the sentences;

calculating, for sentences of the document, a second count that includes a measure of a number of instances in which any of one or more related phrases of the query phrase occurs in the sentences;

calculating, for sentences of the document, a third count that includes a measure of a number of instances in which any of one or more phrase extensions of the query phrase occurs in the sentences, wherein a phrase extension is a super-sequence that begins with the query phrase;

selecting one or more of the sentences of the document based on their respective first, second and third counts; and

forming a description of the document from the selected sentences, wherein a phrase g_j is a related phrase of another phrase g_k where an information gain of g_j with respect to g_k exceeds a predetermined threshold, the information gain being a function of both actual and expected co-occurrence rates of g_j and g_k.

7. A computer implemented system for automatically generating a description of a document, comprising:

a document retrieval system executed by a computer and adapted to retrieve a document in response to a query, the query including a query phase, the document including a plurality of sentences; and

a document description system executed by a computer and adapted to;

calculate, for sentences of the document, a first count that includes a measure of a number of instances in which the query phrase occurs in the sentences;

select one or more of the sentences of the document based on their respective counts, the selecting further comprising;

sorting sentences of the document in declining order of their respective counts, the first count constituting a primary sort key, a second count that includes a measure of a number of instances in which any of one or more related phrases of the query phrase occurs in the respective sentences of the document constituting a secondary sort key, and a third count that includes a measure of a number of instances in which any of one or more phrase extensions of the query phrase occurs in the respective sentences of the document constituting a tertiary sort key, and

selecting a number of the sentences of the document having the highest counts; and

form a description of the document from the selected sentences.

8. The system of claim 7, wherein generating a document description comprising selected sentences of the document, comprises concatenating the selected sentences to form a block of text.

9. The system of claim 7, wherein a phrase g_j is a related phrase of another phrase g_k where an information gain of g_j with respect to g_k exceeds a predetermined threshold, the information gain being a function of both actual and expected co-occurrence rates of g_j and g_k.