Method for node classification and scoring by combining parallel iterative scoring calculation

• US 7,584,183 B2
• Filed: 02/01/2006
• Issued: 09/01/2009
• Est. Priority Date: 02/01/2006
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Hegerty, Ian, Maghoul, Farzin
• Primary Examiner(s): LeRoux; Etienne P
• Assistant Examiner(s): BUI, THUY T
• Application Number:
  US11/346,860
• Publication Number:
  US 20070179943A1
• Time in Patent Office: 1,308 Days
• Field of Search: 707/500, 707/5, 707/3, 707/9, 707/101, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A plurality of documents is scored, where at least some of the documents are characterized by at least one link from at least one other of the documents. For each of at least particular ones of the plurality of documents, a score is assigned to that particular document, with respect to a topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document.

Claims

1. A method of scoring a plurality of documents, where at least some of the documents are characterized by at least one link from at least one other of the documents, the method comprising:

for each of at least particular ones of the plurality of documents, assigning a score to that particular document, with respect to a particular topic, based at least in part on a characterization of topic incoherency associated with at least one document linking, from the at least one document with which the characterization of topic incoherency is associated, to that particular document,

wherein the characterization of topic incoherency of the at least one document linking, from the at least one document with which the characterization of topic incoherency is associated, to that particular document is an indication of an amount of topic-specific score authority for each of multiple topics of the at least one document linking to that particular document,

wherein the higher the topic-specific authority for each of multiple topics of the at least one document linking to that particular document, the indicated topic incoherency associated with the at least one document linking to that particular document is higher;

wherein the score assigned to that particular document is reduced based on higher topic incoherency of the at least one document linking to that particular document; and

wherein the method further comprises

determining a value indicative of a probability of not linking to any of the at least particular ones of the plurality of documents; and

accounting for the determined value with respect to scores of documents other than the at least particular ones of the plurality of documents.

2. The scoring method of claim 1, wherein:

the step of assigning a score to that particular document, with respect to the topic, based at least in part on a characterization of topic incoherency associated with at least one document linking to that particular document includes

treating the characterization of topic incoherency as a weighting factor with respect to assigning a score to that particular document, with respect to the topic.

3. The scoring method of claim 1, wherein:

the step of assigning a score to a particular document, with respect to the topic, based at least in part on a characterization of topic incoherency associated with at least one document linking to that particular document includes;

assigning a score to that particular document, with respect to the topic, based on the score, with respect to the topic, of each of the at least one document linking to that particular document, weighted by the characterization of topic incoherency associated with the at least one document linking to that particular document.

4. The scoring method of claim 1, further comprising:

determining the characterization of topic incoherency associated with each of the at least one document linking to that particular document includes, for each of the at least one document linking to that particular document, processing an indication of topics associated with that linking document.

5. The scoring method of claim 4, wherein:

processing an indication of topics associated with that linking document includes determining the characterization of topic incoherency as a function of scores, with respect to a plurality of topics, for that linking document.

6. The scoring method of claim 5, wherein:

the step of assigning a score to a particular document, with respect to the topic, based at least in part on a characterization of topic incoherency associated with at least one document linking to that particular document includes;

weighting the score assigned to that particular document, for the topic, by the characterization of topic incoherency associated with the at least one document linking to that particular document, so as to result in less weighting of the score assigned to that particular document, for the topic, the greater the number of topics associated with that linking document.

7. The scoring method of claim 6, wherein:

the number of topics associated with that linking document is determined based on a score, with respect to that linking document, for each of the topics associated with that linking document.

8. The scoring method of claim 1, wherein:

the score assigning step is performed iteratively among the plurality of documents.

9. The method of claim 1, further comprising:

repeating the score assigning step for each of the at least particular one of the plurality of documents, for each of a plurality of topics.

10. The method of claim 9, further comprising:

targeting an advertisement to a viewer of a particular page based on the topic scores.

11. The method of claim 9, wherein:

the plurality of topics are counties associated with the documents; and

the method further comprises adjusting a search result based on the topic scores.

12. The method of claim 9, further comprising:

in response to a search query from a user, presenting a plurality of assisted search suggestions, wherein presenting the plurality of assisted search suggestions includes considering preferences of the user relative to determined topic scores for documents chosen by other users in response to particular assisted search suggestions.

13. The method of claim 9, further comprising:

determining for each document a factor that is nominally indicative of whether that document is spammy, including considering topic scores for each document, across a plurality of topics, relative to a link popularity measure for that document.

14. The method of claim 1, wherein:

the characterization of topic incoherency for the document linking to that particular document is adjusted based on a relationship between topics of the linking document to topics of that particular document.

15. The method of claim 14, wherein:

adjusting the characterization of topic incoherency includes indicating a linking document as less coherent, relative to that particular document, based on a generalization or specialization relationship between the topics of the linking document to topics of that particular document.

16. A computing device operable to perform a method of scoring a plurality of documents, where at least some of the documents are characterized by at least one link from at least one other of the documents, the method comprising:

for each of at least particular ones of the plurality of documents, assigning a score to that particular document, with respect to a particular topic, based at least in part on a characterization of topic incoherency associated with at least one document linking, from the at least one document with which the characterization of tonic incoherency is associated, to that particular document,

wherein the characterization of tonic incoherency of the at least one document linking, from the at least one document with which the characterization of topic incoherency is associated, to that particular document is an indication of an amount of topic-specific score authority for each of multiple topics of the at least one document linking to that particular document,

wherein the higher the topic-specific authority for each of multiple topics of the at least one document linking to that particular document, the indicated tonic incoherency associated with the at least one document linking to that particular document is higher;

wherein the score assigned to that particular document is reduced based on higher topic incoherency of the at least one document linking to that particular document; and

wherein the method further comprises

determining a value indicative of a probability of not linking to any of the at least particular ones of the plurality of documents; and

accounting for the determined value with respect to scores of documents other than the at least particular ones of the plurality of documents.

17. A method of operating a computing device to search a network of pages, comprising:

querying to a collection of information about the pages of the network of pages, wherein the collection of information about the pages includes;

an index of the pages; and

a collection of scores for the pages generated according to the steps of;

for each of at least particular ones of the plurality of documents, assigning a score to that particular document, with respect to a particular topic, based at least in part on a characterization of topic incoherency associated with at least one document linking, from the at least one document with which the characterization of topic incoherency is associated, to that particular document,

wherein the characterization of topic incoherency of the at least one document linking, from the at least one document with which the characterization of topic incoherency is associated, to that particular document is an indication of an amount of topic-specific score authority for each of multiple topics of the at least one document linking to that particular document,

wherein the higher the topic-specific authority for each of multiple topics of the at least one document linking to that particular document, the indicated topic incoherency associated with the at least one document linking to that particular document is higher;

wherein the score assigned to that particular document is reduced based on higher topic incoherency of the at least one document linking to that particular document; and

wherein the steps by which the collection of scores for the pages generated further include

determining a value indicative of a probability of not linking to any of the at least particular ones of the plurality of documents; and

accounting for the determined value with respect to scores of documents other than the at least particular ones of the plurality of documents; and

the method of operating the computing device to search a network of pages further comprising receiving, in response to the query, an indication of pages according to the index of pages, ranked according to the collection of scores.

18. The method of claim 17, further comprising:

accessing at least one of the pages indicated by the received indication of pages.

19. A computer program product for scoring a plurality of documents, where at least some of the documents are characterized by at least one link from at least one other of the documents, the computer program product comprising at least one tangible computer-readable medium having computer program instructions stored therein which are operable to cause at least one computing device to:

for each of at least particular ones of the plurality of documents, assign a score to that particular document, with respect to a particular topic, based at least in part on a characterization of topic incoherency associated with at least one document linking, from the at least one document with which the characterization of topic incoherency is associated, to that particular document, wherein the characterization of topic incoherency of the at least one document linking, from the at least one document with which the characterization of topic incoherency is associated, to that particular document is an indication of an amount of topic-specific score authority for each of multiple topics of the at least one document linking to that particular document,

wherein the higher the topic-specific authority for each of multiple topics of the at least one document linking to that particular document, the indicated topic incoherency associated with the at least one document linking to that particular document is higher;

wherein the score assigned to that particular document is reduced based on higher topic incoherency of the at least one document linking to that particular document; and

wherein the computer program instructions are further operable to cause the at least one computing device to

determine a value indicative of a probability of not linking to any of the at least particular ones of the plurality of documents; and

account for the determined value with respect to scores of documents other than the at least particular ones of the plurality of documents.

20. The computer program product of claim 19, wherein:

the computer program instructions operable to cause the at least one computing device to assign a score to that particular document, with respect to the topic, based at least in part on a characterization of topic incoherency associated with at least one document linking to that particular document includes

computer program instructions operable to cause the at least one computing device to treat the characterization of topic incoherency as a weighting factor with respect to assigning a score to that particular document, with respect to the topic.

21. The computer program product of claim 19, wherein:

the computer program instructions operable to cause the at least one computing device to assign a score to a particular document, with respect to the topic, based at least in part on a characterization of topic incoherency associated with at least one document linking to that particular document includes;

computer program instructions operable to cause the at least one computing device to assign a score to that particular document, with respect to the topic, based on the score, with respect to the topic, of each of the at least one document linking to that particular document, weighted by the characterization of topic incoherency associated with the at least one document linking to that particular document.

22. The computer program product of claim 19, wherein:

the computer program instructions further include computer program instructions operable to cause the at least one computing device to determine the characterization of topic incoherency associated with each of the at least one document linking to that particular document includes, for each of the at least one document linking to that particular document, processing an indication of topics associated with that linking document.

23. The computer program product of claim 22, wherein:

the computer program instructions operable to cause the at least one computing device to process an indication of topics associated with that linking document includes computer program instructions operable to cause the at least one computing device to determine the characterization of topic incoherency as a function of scores, with respect to a plurality of topics, for that linking document.

24. The computer program product of claim 23, wherein:

the computer program instructions operable to cause the at least one computing device to assign a score to a particular document, with respect to the topic, based at least in part on a characterization of topic incoherency associated with at least one document linking to that particular document includes;

computer program instructions operable to cause the at least one computing device to weight the score assigned to that particular document, for the topic, by the characterization of topic incoherency associated with the at least one document linking to that particular document, so as to result in less weighting of the score assigned to that particular document, for the topic, the greater the number of topics associated with that linking document.