Detecting novel document content

• US 7,451,120 B1
• Filed: 03/20/2006
• Issued: 11/11/2008
• Est. Priority Date: 03/20/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bharat, Krishna, Kumar, M. Bharath
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US11/378,628
• Time in Patent Office: 967 Days
• Field of Search: None
• 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 computer-implemented method, comprising:

determining an ordered sequence of documents;

determining an amount of novel content contained in each document of the ordered sequence of documents by identifying one or more pairs of textual sequences that occur in close proximity to one another in a respective document;

assigning a novelty score to each document based on the determined amount of novel content; and

providing the documents of the ordered sequence of documents based on the assigned novelty scores.

2. The computer-implemented method of claim 1, wherein the textual sequences comprise one or more of named entities, document title terms, or numbers.

3. The computer-implemented method of claim 1, wherein determining an amount of novel content further comprises:

determining an indication of importance of each of the identified one or more pairs to a respective document of the ordered sequence of documents.

4. The computer-implemented method of claim 3, wherein determining an indication of importance of each of the identified one or more pairs comprises:

determining an importance value I_a(i, A) as equal to TF(i, A),

where i is a pair of the one or more pairs contained in a document A, and

TF(t, A) is a term frequency of the pair i in document A.

5. The computer-implemented method of claim 3, wherein determining an indication of importance of each of the identified one or more pairs comprises:

determining an importance value I_a(i, A) as equal to WTF(i, A),

where i is a pair of the one or more pairs contained in a document A, and

$\mathrm{WTF}<br><br>\left(i,A\right)=\sum <br><br><br><br>\frac{\mathrm{sentences}<br><br><br><br>s<br><br><br><br>\mathrm{containing}<br><br><br><br>\mathrm{pair}<br><br><br><br>i<br><br><br><br>\mathrm{in}<br><br><br><br>A<br><br>}{\sqrt{\mathrm{depth}<br><br><br><br>\mathrm{of}<br><br><br><br>\mathrm{sentence}<br><br><br><br>s<br><br><br><br>\mathrm{in}<br><br><br><br>A}}.$

6. The computer-implemented method of claim 1, wherein determining an amount of novel content further comprises:

determining an indication of importance of each of the identified one or more pairs to the ordered sequence of documents.

7. The computer-implemented method of claim 6, wherein determining the indication of importance of each of the identified one or more pairs comprises:

determining an importance value I_s(i, S) that measures the importance of a pair i of the one or more pairs to the ordered sequence of documents, wherein I_s(i, S) is computed based on one or more of the following quantities;

a) a number of documents in the ordered sequence of documents that contain the pair i;

b) a sum of I_a(i, A) for all documents A in the ordered sequence of documents;

c) a sum of log(I_a(i, A) for all documents A in the ordered sequence of documents;

or

d) N_s(t₁, S)*N_s(t₂, S) for pair i comprising identified textual sequences t₁ and t₂.

8. The computer-implemented method of claim 7, wherein assigning a novelty score to each document comprises:

determining sigma(I_s(i, S)) for all of the one or more pairs that a respective document introduced for a first time in the ordered sequence of documents.

9. The computer-implemented method of claim 7, wherein assigning a novelty score to each document comprises:

determining a sum of improvement values for all of the pairs of the one or more pairs contained in the document, wherein an improvement value for a pair of the one or more pairs of a respective document A comprises one or more of the following;

a) I_s(i, {S₁, A})−

I_s(i, S₁) over all pairs contained in the document;

b) (I_s(i, {S₁, A})−

I_s(i, S₁))/I_s(t, {S₁, A});

or

c) ((I_s(i, {S₁, A})−

I_s(i, S₁))/I_s(t, {S₁, A}))*I_s(i, S),

where S₁ comprises documents in the sequence of documents that are earlier in the sequence than document A.

10. The computer-implemented method of claim 1, further comprising:

ranking the documents based on the assigned novelty scores.

11. The computer-implemented method of claim 10, where the providing includes:

displaying one or more of the documents based on the ranking.

12. A computer-implemented method, comprising:

identifying textual sequences that carry information within a document of a plurality of documents;

determining an importance value N_a(t, A) of each of the identified textual sequences as equal to TF(t, A)*WTF(t, A),

where t is an identified textual sequence contained in the document,

A is the document,

TF(t, A) is the term frequency of textual sequence t in document A, and

$\mathrm{WTF}<br><br>\left(i,A\right)=\sum <br><br><br><br>\frac{\mathrm{sentences}<br><br><br><br>s<br><br><br><br>\mathrm{containing}<br><br><br><br>\mathrm{pair}<br><br><br><br>i<br><br><br><br>\mathrm{in}<br><br><br><br>A<br><br>}{\sqrt{\mathrm{depth}<br><br><br><br>\mathrm{of}<br><br><br><br>\mathrm{sentence}<br><br><br><br>s<br><br><br><br>\mathrm{in}<br><br><br><br>A}};<br><br>$

assigning a score to the document of the plurality of documents based on the importance value of each of the identified textual sequences to the document, the assigned score indicating the presence of content in the document that is novel relative to content in other documents of the plurality of documents;

ranking the document among the other documents of the plurality of documents based on the assigned score; and

displaying the document among other documents based on the ranking.

13. The method of claim 12, wherein the textual sequences comprise one or more of named entities, document title terms, or numbers.

14. The computer-implemented method of claim 12, wherein assigning a score to a document further comprises:

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

15. The computer-implemented method of claim 14, further comprising:

determining an indication of importance of each of the identified one or more pairs to the document.

16. The computer-implemented method of claim 15, wherein determining an indication of importance of each of the identified one or more pairs comprises:

determining an importance value I_a(i, A) as equal to WTF(i, A),

where i is a pair of the one or more pairs contained in the document, A is the document, and

$\mathrm{WTF}<br><br>\left(i,A\right)=\sum <br><br><br><br>\frac{\mathrm{sentences}<br><br><br><br>s<br><br><br><br>\mathrm{containing}<br><br><br><br>\mathrm{pair}<br><br><br><br>i<br><br><br><br>\mathrm{in}<br><br><br><br>A<br><br>}{\sqrt{\mathrm{depth}<br><br><br><br>\mathrm{of}<br><br><br><br>\mathrm{sentence}<br><br><br><br>s<br><br><br><br>\mathrm{in}<br><br><br><br>A}}.$

17. The computer-implemented method of claim 12, wherein assigning a score to a document further comprises:

determining an indication of importance of each of the identified textual sequences to the plurality of documents.

18. The computer-implemented method of claim 17, wherein determining an indication of importance of each of the identified textual sequences to the plurality of documents comprises:

determining an importance value N_s(t, A) that measures the importance of an identified textual sequence t to the plurality of documents, wherein N_s(t, A) is computed based on one or more of the following quantities;

a) a number of documents in the plurality of documents that contain the identified textual sequence t;

b) a sum of N_a(t, A) for all documents A in the plurality of documents;

c) a sum of log(N_a(t, A)) for all documents A in the plurality of documents;

d) a sum of I_a(i, S) over all interactions i in the plurality of documents that involve identified textual sequence t;

or

e) a sum of M_a(i, S) over all interactions i in the plurality of documents that involve the identified textual sequence t, wherein M_a(i, S) is the maximum I_a(i, A) over all documents A in the plurality of documents.

19. The computer-implemented method of claim 14, wherein assigning a score to a document further comprises:

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

20. The method of claim 19, wherein determining the indication of importance of each of the identified one or more pairs to the plurality of documents comprises:

determining an importance value I_s(i, S) that measures the importance of a pair i of the one or more pairs to the plurality of documents, wherein I_s(i, S) is computed based on one or more of the following quantities;

a) a number of documents in the plurality of documents that contain the pair i;

b) a sum of I_a(i, A) for all documents A in the plurality of documents;

c) a sum of log(I_a(i, A)) for all documents A in the plurality of documents;

d) N_s(t₁, S)*Ns(t₂, S) for pair i comprising identified textual sequences t₁ and t₂.

21. The computer-implemented method of claim 20, wherein assigning a score to a document further comprises:

measuring an indication of importance of the document relative to the plurality of documents.

22. The computer-implemented method of claim 19, wherein measuring an importance of the document comprises:

determining sigma (N_s(t, S)) for all identified textual sequences t that the document introduced for the first time in the plurality of documents.

23. The computer-implemented method of claim 21, wherein measuring an indication of importance of the document comprises:

determining sigma (I_s(i, S)) for all of the one or more pairs that the document introduced for a first time in the plurality of documents.

24. The computer-implemented method of claim 21, wherein measuring an indication of importance of the document comprises:

determining a sum of improvement values for all of the identified textual sequences contained in the document, wherein an improvement for an identified textual sequence t of the document A comprises one or more of the following;

a) N_s(t, {S₁, A})−

N_s(t, S₁) over all identified textual sequences contained in the document A;

b) (N_s(t, {S₁, A})−

N_s(t, S₁))/N_s(t, {S₁, A});

or

c) ((N_s(t, {S₁, A})−

N_s(t, S₁))/N_s(t, {S₁, A}))*N_s(t, S),

where S₁ comprises documents in the sequence of documents that are temporally earlier in the plurality of documents than document A.

25. The computer-implemented method of claim 21, wherein measuring an indication of importance of the document comprises:

determining a sum of improvement values for all of the pairs of the one or more pairs contained in the document, wherein an improvement for a pair of the one or more pairs for the document A comprises one or more of the following;

a) I_s(i, {S₁, A})−

Is(i, S₁) over all pairs contained in the document A;

b) I_s(i, {S₁, A})−

I_s(i, S₁))I_s(t, {S₁, A));

or

c) ((I_s(i, {S₁, A})−

I_s(i, S₁))/I_s(t, {S₁, A}))*I_s(i, S),

where S₁ comprises documents in the sequence of documents that are temporally earlier in the plurality of documents than document A.

26. A computer-implemented method, comprising:

identifying one or more textual sequences that carry information in a document of a plurality of documents;

determining an indication of importance of each of the textual sequences relative to the plurality of documents;

assigning a score to the document based on the determined indication of importance of each of the textual sequences; and

providing the document among other documents based on the assigned score.

27. The computer-implemented method of claim 26, further comprising:

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

28. The computer-implemented method of claim 27, where the providing includes:

displaying the document among other documents based on the ranking.

29. The computer-implemented method of claim 26, further comprising:

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

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

30. The computer-implemented method of claim 29, wherein assigning the score to the document is further based on the determined importance of each of the one or more pairs.

31. A computer-readable memory device that stores computer-executable instructions, comprising:

instructions for obtaining an ordered sequence of documents;

instructions for determining an amount of novel content contained in each document of the ordered sequence of documents by identifying one or more pairs of textual sequences that occur in close proximity to one another in a respective document;

instructions for assigning novelty scores to the documents based on the determined amount of novel content; and

instructions for providing the documents of the ordered sequence of documents based on the assigned novelty scores.

32. A computer-implemented system, comprising:

means for identifying one or more textual sequences that carry information in a document of a plurality of documents;

means for determining an indication of importance of each of the textual sequences relative to the plurality of documents;

means for assigning a score to the document based on the determined indication of importance of each of the textual sequences; and

means for providing the document among other documents based on the assigned score.