Detecting novel document content

• US 8,140,449 B1
• Filed: 10/03/2008
• Issued: 03/20/2012
• Est. Priority Date: 03/20/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kumar, M. Bharath, Bharat, Krishna
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US12/245,166
• Time in Patent Office: 1,264 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system determines an ordered sequence of documents and determines an amount of novel content contained in each document of the ordered sequence of documents. The system assigns a novelty score to each document based on the determined amount of novel content.

Claims

1. A method implemented by one or more computing devices, the method comprising:

identifying, by a processor of one of the one or more computing devices, a temporally-ordered sequence of documents based on a search query received from a client device;

identifying, by a processor of one of the one or more computing devices, in a particular document of the temporally-ordered sequence of documents, novel content including content not present in other documents of the temporally-ordered sequence of documents;

assigning, by a processor of one of the one or more computing devices, a score to the particular document based on an amount of the novel content in the particular document; and

ranking, by a processor of one of the one or more computing devices, the particular document among the temporally-ordered sequence of documents based on the assigned score.

2. The method of claim 1, where assigning the score to the particular document comprises:

identifying, by a processor of one of the one or more computing devices, one or more textual sequences in the particular document; and

determining, by a processor of one of the one or more computing devices, an indication of importance, to the particular document, of each of the one or more textual sequences.

3. The method of claim 2, where determining the indication of importance, to the particular document, of each of the one or more textual sequences, comprises:

identifying, by a processor of one of the one or more computing devices, one or more pairs of the one or more textual sequences that occur within a paragraph of one another in the particular document; and

estimating, by a processor of one of the one or more computing devices, an indication of importance of each of the one or more pairs relative to the particular document.

4. The method of claim 3, where the indication of importance of each of the one or more pairs relative to the particular document is based on one or more of:

a number of occurrences of each of the one or more pairs in the particular document, or

depths of sentences, within the document, including the one or more pairs.

5. The method of claim 2, where assigning the score to the particular document further comprises:

determining an indication of importance, to the sequence of documents, of each of the one or more textual sequences.

6. The method of claim 1, further comprising:

identifying, by a processor of one of the one or more computing devices, one or more textual sequences in the particular document; and

determining, by a processor of one of the one or more computing devices, an indication of importance, to the sequence of documents, of each of the one or more textual sequences.

7. The method of claim 6, where determining the indication of importance, to the sequence of documents, of each of the one or more textual sequences is based on one or more of:

a number of documents in the sequence of documents that contain the textual sequence,

a sum of instances of the textual sequence for all of the documents in the sequence of documents, or

a sum of an importance value over all pairs that involve the textual sequence.

8. A memory device that stores computer-executable instructions, the memory device comprising:

instructions for obtaining one or more textual sequences from a document of a sequence of documents;

instructions for identifying one or more pairs of the one or more textual sequences that occur within a paragraph of one another in the document;

instructions for identifying, based on the one or more textual sequences and the one or more pairs, a presence of novel content in the document where the novel content includes content that does not occur in other documents in the sequence of documents; and

instructions for assigning a score to the document based on the identified novel content of the document.

9. The memory device of claim 8, where the sequence of documents includes a temporally-ordered cluster of news documents.

10. The memory device of claim 8, where the sequence of documents comprises a temporally-ordered sequence of documents.

11. The memory device of claim 8, where each of the one or more textual sequences comprises one or more of named entities, document title terms, or numbers.

12. The memory device of claim 8, further comprising:

instructions for ranking the document among the sequence of documents based on the assigned score.

13. A computer-implemented method, comprising:

identifying, by a processor, in a document of a plurality of documents, one or more textual sequences;

identifying, by the processor, based on the one or more textual sequences, a presence of novel content in the document where the novel content includes content that does not occur in other documents of the plurality of documents;

assigning, by the processor, a score to the document based on the identified novel content including each of the one or more textual sequences; and

ranking, by the processor, the document among the plurality of documents based on the assigned score.

14. The computer-implemented method of claim 13, where each of the one or more textual sequences comprises one or more of a named entity, a document title term, or a number.

15. The computer-implemented method of claim 13, where identifying the presence of novel content further comprises:

determining an indication of importance of each of the one or more textual sequences to the document.

16. The computer-implemented method of claim 13, where identifying one or more textual sequences comprises:

identifying one or more pairs of the one or more textual sequences that occur in close proximity to one another in the document.

17. The computer-implemented method of claim 16, where identifying the presence of novel content further comprises:

determining an importance of each of the identified one or more pairs to the plurality of documents.

18. The computer-implemented method of claim 13, further comprising:

providing one or more of the plurality of documents, for display, based on the ranking.

19. The computer-implemented method of claim 13, where the plurality of documents includes a cluster of news documents.

20. The computer-implemented method of claim 13, where identifying the presence of novel content further comprises:

identifying a time associated with the document; and

estimating an indication of importance of each of the one or more textual sequences in the document to a respective document of the plurality of documents, where the respective document is selected from a subset of the plurality of documents within a particular range of the identified time.