Scoring documents in a linked database

• US 8,195,651 B1
• Filed: 02/02/2010
• Issued: 06/05/2012
• Est. Priority Date: 01/10/1997
• Status: Expired due to Term

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Page, Lawrence
• Primary Examiner(s): Le, Uyen T.
• Application Number:
  US12/698,803
• Time in Patent Office: 854 Days
• Field of Search: None
• US Class Current: 707/723
• CPC Class Codes: G06F 16/382 using citations hypermedia G06F16/94
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method assigns importance ranks to nodes in a linked database, such as any database of documents containing citations, the world wide web or any other hypermedia database. The rank assigned to a document is calculated from the ranks of documents citing it. In addition, the rank of a document is calculated from a constant representing the probability that a browser through the database will randomly jump to the document. The method is particularly useful in enhancing the performance of search engine results for hypermedia databases, such as the world wide web, whose documents have a large variation in quality.

Claims

1. A method performed by a computer, the method comprising:

identifying, by the computer, links from linking documents to linked documents in a network;

determining, by the computer, a measure of importance of the identified links;

assigning, by the computer, a weight value to each of the identified links based on the determined measure of importance of the identified link;

assigning, by the computer, a score to one of the linked documents based on the weight value assigned to one or more of the identified links that point to the one of the linked documents; and

storing, by the computer, the score for the one of the linked documents.

2. The method of claim 1, where the measure of importance, of each of the identified links, is based on a measure of quality associated with the corresponding linking document.

3. The method of claim 1, where the linking documents and the linked documents comprise at least a million documents on the world wide web.

4. The method of claim 1, where the measure of importance, of each of the identified links, is based on whether the corresponding linking document is stored on a same server as the linked document.

5. The method of claim 1, where the measure of importance, of each of the identified links, is based on a measure of importance of a location at which the corresponding linking document is stored.

6. The method of claim 1, where the measure of importance, of each of the identified links, is based on a position of the identified link within the corresponding linking document.

7. The method of claim 1, where the measure of importance, of each of the identified links, is based on a visibility of the identified link within the corresponding linking document relative to a visibility of another link within the corresponding linking document.

8. The method of claim 7, where the visibility, of the identified link within the corresponding linking document, is associated with a font size of text associated with the identified link.

9. The method of claim 1, where the measure of importance, of each of the identified links, is based on a date on which the corresponding linking document was last modified.

10. The method of claim 1, where the measure of importance, of each of the identified links, is based on user behavior with regard to a parameter associated with the identified link within the corresponding linking document.

11. A method performed by a computer, the method comprising:

identifying documents in a network;

scoring the identified documents based on scores of documents pointing to the identified documents and a damping factor used to avoid loops when scoring the identified documents; and

storing scores for the identified documents.

12. The method of claim 11, where the documents include at least a million documents on the world wide web.

13. A method performed by a computer, the method comprising:

identifying, by the computer, documents in a network;

scoring, by the computer, the identified documents based on scores of documents pointing to the identified documents and a component representing a random jump between documents in the network; and

storing, by the computer, scores for the identified documents.

14. The method of claim 13, where the documents include at least a million documents on the world wide web.

15. A method performed by a computer, the method comprising:

identifying, by the computer, at least a million documents on the world wide web;

generating, by the computer, scores for the identified documents, the score, for one of the identified documents, being based on a respective score of each of a plurality of the identified documents that includes a link to the one of the identified documents and a respective quality of links originating from each of the plurality of the identified documents; and

storing, by the computer, the scores for the identified documents.

16. The method of claim 15, where the score, for the one of the identified documents, is further based on a total quantity of the identified documents.

17. The method of claim 15, where the score, for the one of the identified documents, is based on respective values corresponding to the plurality of the identified documents,

the respective value, corresponding to one of the plurality of the identified documents, including the respective score associated with the one of the plurality of the identified documents divided by the respective quantity of links originating from the one of the plurality of the identified documents.

18. The method of claim 15, where the score, for the one of the identified documents, is based on a summation of respective values corresponding to the plurality of the identified documents,

the respective value, corresponding to one of the plurality of the identified documents, including the respective score associated with the one of the plurality of the identified documents divided by the respective quantity of links originating from the one of the plurality of the identified documents.

19. The method of claim 15, where the score, for the one of the identified documents, is further based on a value that reflects a probability that a surfer will randomly jump to any one of the identified documents rather than selecting a link from a particular one of the identified documents.

20. The method of claim 19, where the probability, for the one of the identified documents, differs from a probability for another one of the identified documents.